Minimizing the object dimensions in circle and sphere packing problems

Given a fixed set of identical or different-sized circular items, the problem we deal with consists on finding the smallest object within which the items can be packed. Circular, triangular, squared, rectangular and also strip objects are considered. Moreover, 2D and 3D problems are treated. Twice-differentiable models for all these problems are presented. A strategy to reduce the complexity of evaluating the models is employed and, as a consequence, instances with a large number of items can be considered. Numerical experiments show the flexibility and reliability of the new unified approach. (C) 2007 Elsevier Ltd. All rights reserved.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

THE LOWER CENTRAL AND DERIVED SERIES OF THE BRAID GROUPS OF THE FINITELY-PUNCTURED SPHERE

Motivated in part by the study of Fadell-Neuwirth short exact sequences, we determine the lower central and derived series for the braid groups of the finitely-punctured sphere. For n >= 1, the class of m-string braid groups B(m)(S(2)\{x(1), ... , x(n)}) of the n-punctured sphere includes the usual Artin braid groups B(m) (for n = 1), those of the annulus, which are Artin groups of type B (for n = 2), and affine Artin groups of type (C) over tilde (for n = 3). We first consider the case n = 1. Motivated by the study of almost periodic solutions of algebraic equations with almost periodic coefficients, Gorin and Lin calculated the commutator subgroup of the Artin braid groups. We extend their results, and show that the lower central series (respectively, derived series) of B(m) is completely determined for all m is an element of N (respectively, for all m not equal 4). In the exceptional case m = 4, we obtain some higher elements of the derived series and its quotients. When n >= 2, we prove that the lower central series (respectively, derived series) of B(m)(S(2)\{x(1), ... , x(n)}) is constant from the commutator subgroup onwards for all m >= 3 (respectively, m >= 5). The case m = 1 is that of the free group of rank n - 1. The case n = 2 is of particular interest notably when m = 2 also. In this case, the commutator subgroup is a free group of infinite rank. We then go on to show that B(2)(S(2)\{x(1), x(2)}) admits various interpretations, as the Baumslag-Solitar group BS(2, 2), or as a one-relator group with non-trivial centre for example. We conclude from this latter fact that B(2)(S(2)\{x(1), x(2)}) is residually nilpotent, and that from the commutator subgroup onwards, its lower central series coincides with that of the free product Z(2) * Z. Further, its lower central series quotients Gamma(i)/Gamma(i+1) are direct sums of copies of Z(2), the number of summands being determined explicitly. In the case m >= 3 and n = 2, we obtain a presentation of the derived subgroup, from which we deduce its Abelianization. Finally, in the case n = 3, we obtain partial results for the derived series, and we prove that the lower central series quotients Gamma(i)/Gamma(i+1) are 2-elementary finitely-generated groups.

The classification and the conjugacy classes of the finite subgroups of the sphere braid groups

Let n >= 3. We classify the finite groups which are realised as subgroups of the sphere braid group B(n)(S(2)). Such groups must be of cohomological period 2 or 4. Depending on the value of n, we show that the following are the maximal finite subgroups of B(n)(S(2)): Z(2(n-1)); the dicyclic groups of order 4n and 4(n - 2); the binary tetrahedral group T*; the binary octahedral group O*; and the binary icosahedral group I(*). We give geometric as well as some explicit algebraic constructions of these groups in B(n)(S(2)) and determine the number of conjugacy classes of such finite subgroups. We also reprove Murasugi`s classification of the torsion elements of B(n)(S(2)) and explain how the finite subgroups of B(n)(S(2)) are related to this classification, as well as to the lower central and derived series of B(n)(S(2)).