Hardness of lazy packing and covering

We prove APX-hardness for the two problems maximum resource bin packing and lazy bin covering. Simple algorithms matching the best absolute bounds under the assumption P≠NP are also derived.     

Lattice packing and covering of convex bodies

The aim of this article is twofold. First, to indicate briefly major problems and developments dealing with lattice packings and coverings of balls and convex bodies. Second, to survey more recent results on uniqueness of lattice packings and coverings of extreme density, on characterization of local minima and maxima of the density and on estimates of the kissing number. Emphasis is on results in general dimensions.     

Fast approximation of matroid packing and covering

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If \(\mathcal {M}\) is a matroid over a set of elements S with independent set \(\mathcal {I}\), and \(m=|S|\), we suppose that we are given an oracle function that takes an independent set \(A\in \mathcal {I}\) and an element \(e\in S\) and determines if \(A\cup \{e\}\) is independent in time I(m). Also, given that the elements of A are represented in an ordered way \(A=\{A_1,\dots ,A_k\}\), we denote the time to check if \(A\cup \{e\}\notin \mathcal {I}\) and if so, to find the minimum \(i\in \{0,\dots ,k\}\) such that \(\{A_1,\dots ,A_i\}\cup \{e\}\notin \mathcal {I}\) by \(I^*(m)\). Then, we describe a new FPTAS that computes for any \(\varepsilon >0\) and for any matroid \(\mathcal {M}\) of rank r over a set S of m elements, in memory space O(m), the packing \(\varLambda ({\mathcal {M}})\) within \(1+\varepsilon \) in time \(O(mI^*(m)\log (m)\log (m/r)/\varepsilon ^2)\), and the covering \(\varUpsilon ({\mathcal {M}})\) in time \(O(r\varUpsilon ({\mathcal {M}})I(m)\log (m)\log (m/r)/\varepsilon ^2)\). This method outperforms in time complexity by a factor of \(\varOmega (m/r)\) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of \(\varOmega (m)\) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The applications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others.     

Some basic properties of packing and covering constants

This article concerns packings and coverings that are formed by the application of rigid motions to the members of a given collectionK of convex bodies. There are two possibilities to construct such packings and coverings: One may permit that the convex bodies fromK are used repeatedly, or one may require that these bodies should be used at most once. In each case one can define the packing and covering constants ofK as, respectively, the least upper bound and the greatest lower bound of the densities of all such packings and coverings. Three theorems are proved. First it is shown that there exist always packings and coverings whose densities are equal to the corresponding packing and covering constants. Then, a quantitative continuity theorem is proved which shows in particular that the packing and covering constants depend, in a certain sense, continuously onK. Finally, a kind of a transference theorem is proved, which enables one to evaluate the packing and covering constants when no repetitions are allowed from the case when repetitions are permitted. Furthermore, various consequences of these theorems are discussed.Supported by National Science Foundation Research Grant DMS 8300825.     

Aggregation-based cutting-planes for packing and covering integer programs

Mathematical Programming - In this paper, we study the strength of Chvátal–Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs)....     

The simultaneous packing and covering constants in the plane

In 1950, C.A. Rogers introduced and studied two simultaneous packing and covering constants for a convex body and obtained the first general upper bound. Afterwards, these constants have attracted the interests of many authors because, besides their own geometric significance, they are closely related to the packing densities and the covering densities of the convex body, especially to the Minkowski-Hlawka theorem. However, so far our knowledge about them is still very limited. In this paper we will determine the optimal upper bound of the simultaneous packing and covering constants for two-dimensional centrally symmetric convex domains, and characterize the domains attaining this upper bound.     

A new sphere packing in 20 dimensions

We construct a new nonlattice sphere packing in 20 dimensions which is denser than any 20-dimensional packing previously known. Properties of the new sphere packing are investigated.Oblatum 24-VI-1994 & 20-1-1995The author was partially supported by the NSF grant NCR 94-09688.     

Hardness of approximation for orthogonal rectangle packing and covering problems

Bansal and Sviridenko [N. Bansal, M. Sviridenko, New approximability and inapproximability results for 2-dimensional bin packing, in: Proceedings of the 15th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 189–196] proved that there is no asymptotic PTAS for 2-dimensional Orthogonal Bin Packing (without rotations), unless P=NP. We show that similar approximation hardness results hold for several 2- and 3-dimensional rectangle packing and covering problems even if rotations by ninety degrees are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm. Our hardness results apply to the most studied case of 2-dimensional problems with unit square bins, and for 3-dimensional strip packing and covering problems with a strip of unit square base.     

On small packing and covering designs with block size 4

A packing (respectively covering) design of order v, block size k, and index λ is a collection of k-element subsets, called blocks, of a v-set, V, such that every 2-subset of V occurs in at most (at least) λ blocks. The packing (covering) problem is to determine the maximum (minimum) number of blocks in a packing (covering) design. Motivated by the recent work of Assaf [1] [2], we solve the outstanding packing and covering problems with block size 4.     

On packing and covering polyhedra of consecutive ones circulant clutters

Building on work by G. Cornuéjols and B. Novick and by L. Trotter, we give different characterizations of contractions of consecutive ones circulant clutters that give back consecutive ones circulant clutters. Based on a recent result by G. Argiroffo and S. Bianchi, we then arrive at characterizations of the vertices of the fractional set covering polyhedron of these clutters. We obtain similar characterizations for the fractional set packing polyhedron using a result by F.B. Shepherd, and relate our findings with similar ones obtained by A. Wagler for the clique relaxation of the stable set polytope of webs. Finally, we show how our results can be used to obtain some old and new results on the corresponding fractional set covering polyhedron using properties of Farey series. Our results do not depend on Lehman’s work or blocker/antiblocker duality, as is traditional in the field.     

Improved sphere packing lower bounds from Hurwitz lattices

In this paper we prove an asymptotic lower bound for the sphere packing density in dimensions divisible by four. This asymptotic lower bound improves on previous asymptotic bounds by a constant factor and improves not just lower bounds for the sphere packing density, but also for the lattice sphere packing density and, in fact, the Hurwitz lattice sphere packing density.     

Finite and uniform stability of sphere coverings

By attaching cables to the centers of the balls and certain intersections of the boundaries of the balls of a ball covering ofE ^d with unit balls, we can associate to any ball covering a collection of cabled frameworks. It turns out that a finite subset of balls can be moved, maintaining the covering property, if and only if the corresponding finite subframework in one of the cabled frameworks is not rigid. As an application of this cabling technique we show that the thinnest cubic lattice sphere covering ofE ^d is not finitely stable. The first two authors were partially supported by the Hungarian National Science Foundation under Grant No. 326-0413.     

An inequality linking packing and covering densities of plane convex bodies

For every convex body K in R ², let (K) denote the packing density of K, i.e. the density of the tightest packing of congruent copies of K in R ², and let (K) denote the covering density of K, i.e. the density of the thinnest covering of R ² with congruent copies of K. It is shown here that 4(K)3(K) for every convex body K in R ². This inequality is the strongest possible, since if E is an ellipse, then the equality 4(E)=3(E) holds. Two corollaries are presented, and a summary of known bounds for packing and covering densities is given.