Some Multiply Derived Translation Planes with SL(2,5) as an Inherited Collineation Group in the Translation Complement

Finite translation planes having a collineation group isomorphic to SL(2,5) occur in many investigations on minimal normal non-solvable subgroups of linear translation complements. In this paper, we are looking for multiply derived translation planes of the desarguesian plane which have an inherited linear collineation group isomorphic to SL(2,5). The Hall plane and some of the planes discovered by Prohaska [10], see also [1], are translation planes of this kind of order q ²;, provided that q is odd and either q ²; 1 mod 5 or q is a power of 5. In this paper the case q ² -1 mod 5 is considered and some examples are constructed under the further hypothesis that either q 2 mod 3, or q 1 mod 3 and q 1 mod 4, or q -1 mod 4, 3 q and q 3,5 or 6 mod 7. One might expect that examples exist for each odd prime power q. But this is not always true according to Theorem 2.     

All-norm approximation algorithms

A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different ℓ_p norms. We address this problem by introducing the concept of an all-norm ρ-approximation algorithm, which supplies one solution that guarantees ρ-approximation to all ℓ_p norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each job is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [Math. Program. 46 (1990) 259–271] showed a 2-approximation algorithm for the problem with respect to the ℓ_∞ norm. For any fixed ℓ_p norm the previously known approximation algorithm has a performance of θ(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given ℓ_p norm (p>1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given ℓ_p norm a FPTAS for any fixed number of machines.     

The benefit of preemption with respect to the ℓp norm

We establish tight bounds on the benefit of preemption with respect to the ${?}_p$ norm minimization objective for identical machines and for two uniformly related machines (based on their speed ratio). This benefit of preemption is the supremum ratio between the optimal costs of non-preemptive and preemptive schedules.     

Betti numbers and degree bounds for some linked zero-schemes

In [J. Herzog, H. Srinivasan, Bounds for multiplicities, Trans. Amer. Math. Soc. 350 (1998) 2879-2902], Herzog and Srinivasan study the relationship between the graded Betti numbers of a homogeneous ideal I in a polynomial ring R and the degree of I. For certain classes of ideals, they prove a bound on the degree in terms of the largest and smallest Betti numbers, generalizing results of Huneke and Miller in [C. Huneke, M. Miller, A note on the multiplicity of Cohen-Macaulay algebras with pure resolutions, Canad. J. Math. 37 (1985) 1149-1162]. The bound is conjectured to hold in general; we study this using linkage. If R/I is Cohen-Macaulay, we may reduce to the case where I defines a zero-dimensional subscheme Y. If Y is residual to a zero-scheme Z of a certain type (low degree or points in special position), then we show that the conjecture is true for I_Y.