Simultaneous Packing and Covering in the Euclidean Plane

 In this article we study the simultaneous packing and covering constants of two-dimensional centrally symmetric convex domains. Besides an identity result between translative case and lattice case and a general upper bound, exact values for some special domains are determined. Similar to Mahler and Reinhardt’s result about packing densities, we show that the simultaneous packing and covering constant of an octagon is larger than that of a circle.     

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.     

New classes of fast lower bounds for bin packing problems

The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general framework for establishing new bounds. Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001     

Normal families of covering maps

Suppose that (f _n)n∈N is a sequence of meromorphic covering maps which is uniformly convergent in a neighbourhood of a pointx∈Ĉ such that the limit function is non-constant. It is proved that the convergence extends to the largest domain where the sequence eventually is defined and that the limit function again is a covering map. As a consequence of this result, we obtain a rescaling lemma for holomorphic covering maps, a version of the Carathéodory Kernel Theorem for arbitrary domains in the sphere, and an elementary access to the Riemann Uniformization Theorem for arbitrary domains in the sphere. An application to complex dynamics of transcendental entire functions provides that the existence of an invariant Baker domain implies a certain frequency of singularities of the inverse function.     

On the Packing Densities and the Covering Densities of the Cartesian Products of Convex Bodies

In this article we study the following problem: Is the covering (packing) density of a Cartesian product of two convex bodies always equal to the product of their corresponding covering (packing) densities? For the covering case we get a negative answer. For the packing case we get a combinatorial version which seems to be important for its own interest.     

On the Packing Densities and the Covering Densities of the Cartesian Products of Convex Bodies

In this article we study the following problem: Is the covering (packing) density of a Cartesian product of two convex bodies always equal to the product of their corresponding covering (packing) densities? For the covering case we get a negative answer. For the packing case we get a combinatorial version which seems to be important for its own interest.     

Packing and covering a tree by subtrees

For two polyhedra associated with packing subtrees of a tree, the structure of the vertices is described, and efficient algorithms are given for optimisation over the polyhedra. For the related problem of covering a tree by subtrees, a reduction to a packing problem, and an efficient algorithm are presented when the family of trees is “fork-free”.     

Linear parabolic equations with strong singular potentials

Using an extension of a recent method of Cabré and Martel (1999), we extend the blow-up and existence result in the paper of Baras and Goldstein (1984) to parabolic equations with variable leading coefficients under almost optimal conditions on the singular potentials. This problem has been left open in Baras and Goldstein. These potentials lie at a borderline case where standard theories such as the strong maximum principle and boundedness of weak solutions fail. Even in the special case when the leading operator is the Laplacian, we extend a recent result in Cabré and Martel from bounded smooth domains to unbounded nonsmooth domains.

     

Packing of Incongruent Circles on the Sphere

 In this paper we provide an upper bound to the density of a packing of circles on the sphere, with radii selected from a given finite set. This bound is precise, e.g. for the system of incircles of Archimedean tilings (4, 4, n) with n ? 6. A generalisation to the weighted density of packing is applied to problems of solidity of a packing of circles. The simple concept of solidity was introduced by L. Fejes Toóth [6]. In particular, it is proved that the incircles of the faces of the Archimedean tilings (4,6,6), (4,6,8) and (4, 6, 10) form solid packings. (Received 21 August 2000; in revised form 21 March 2001)     

A note on online hypercube packing

In this paper, we study an online multi-dimensional bin packing problem where all items are hypercubes. Hypercubes of different size arrive one by one, and we are asked to pack each of them without knowledge of the next pieces so that the number of bins used is minimized. Based on the techniques from one dimensional bin packing and specifically the algorithm Super Harmonic by Seiden (J ACM 49:640–671, 2002), we extend the framework for online bin packing problems developed by Seiden to the hypercube packing problem. To the best of our knowledge, this is the first paper to apply a version of Super Harmonic (and not of the Improved Harmonic algorithm) for online square packing, although the Super Harmonic has been already known before. Note that the best previous result was obtained by Epstein and van Stee (Acta Inform 41(9):595–606, 2005b) using an instance of Improved Harmonic. In this paper we show that Super Harmonic is more powerful than Improve Harmonic for online hypercube packing, and then we obtain better upper bounds on asymptotic competitive ratios. More precisely, we get an upper bound of 2.1187 for square packing and an upper bound of 2.6161 for cube packing, which improve upon the previous upper bounds 2.24437 and 2.9421 (Epstein and van Stee in Acta Inform 41(9):595–606, 2005b) for the two problems, respectively.     

Smoothed analysis of integer programming

We present a probabilistic analysis of integer linear programs (ILPs). More specifically, we study ILPs in a so-called smoothed analysis in which it is assumed that first an adversary specifies the coefficients of an integer program and then (some of) these coefficients are randomly perturbed, e.g., using a Gaussian or a uniform distribution with small standard deviation. In this probabilistic model, we investigate structural properties of ILPs and apply them to the analysis of algorithms. For example, we prove a lower bound on the slack of the optimal solution. As a result of our analysis, we are able to specify the smoothed complexity of classes of ILPs in terms of their worst case complexity. This way, we obtain polynomial smoothed complexity for packing and covering problems with any fixed number of constraints. Previous results of this kind were restricted to the case of binary programs.      

A characterization of edge-perfect graphs and the complexity of recognizing some combinatorial optimization games

We characterize edge-perfect graphs and prove that it is co-NP-complete to recognize them. In consequence, recognizing the defining matrices of totally balanced packing games is also co-NP-complete, in contrast with the polynomiality for the covering case. In addition, we solve the computational complexity of universally balanced (with respect to the resources constraints) packing games.     

Covering a polygonal region by rectangles

The problem of covering a compact polygonal region, called target region, with a finite family of rectangles is considered. Tools for mathematical modeling of the problem are provided. Especially, a function, called Γ-function, is introduced which indicates whether the rectangles with respect to their configuration form a cover of the target region or not. The construction of the Γ-function is similar to that of Φ-functions which have been proved to be an efficient tool for packing problems. A mathematical model of the covering problem based on the Γ-function is proposed as well as a solution strategy. The approach is illustrated by an example and some computational results are presented.     

On Free Planes in Lattice Ball Packings

This note, by studying the relations between the length of theshortest lattice vectors and the covering minima of a lattice,proves that for every d-dimensional packing lattice of ballsone can find a four-dimensional plane, parallel to a latticeplane, such that the plane meets none of the balls of the packing,provided that the dimension d is large enough. Nevertheless,for certain ball packing lattices, the highest dimension ofsuch ‘free planes’ is far from d.     

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.     

Multiple solutions for quasilinear elliptic problems¶in ℝ2 with exponential growth

By combining techniques of nonsmooth critical point theory with a sharp estimate of Trudinger–Moser type, we prove the existence of an infinite number of solutions for a class of perturbed symmetric elliptic problems at exponential growth in ℝ² covering the full range of subcriticality allowed. Received: 26 February 2001     

On a question of K. Bezdek and T. Odor on Γ-parallelotops

K. Bezdek and T. Odor proved the following statement in [1]: If a covering ofE ³ is a lattice packing of the convex compact bodyK with packing lattice Λ (K is a Λ-parallelotopes) then there exists such a 2-dimensional sublattice Λ′ of Λ which is covered by the set ∪(K+z∣z ∈ Λ′). (K ∪L(Λ′) is a Λ′-parallelotopes). We prove that the statement is not true in the case of the dimensionsn=6, 7, 8. Supported by Hung. Nat. Found for Sci. Research (OTKA) grant no. 1615 (1991).     

A Remark about Peck’s Method in Positive Characteristic

 In this short paper, we study Peck’s method in positive characteristic. Curiously enough, the simultaneous approximations this method provides are better than in the real field. (Received 11 January 2001; in revised form 26 March 2001)     

Path coverings with paths

In this paper, we give two new proofs of a result of Heinrich, Langdeau and Verrall that provide necessary and sufficient conditions for the existence of a set S of 3‐paths in K_n having the property that each 2‐path in K_n lies in exactly one path in S. These are then used to consider the case n ≡ 3 (mod 4) when no such exact covering is possible, and to solve the problem of covering (k−1)‐paths with k‐paths for all k ≥ 3. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 156–167, 2001     

A Concentration Theorem for the Heat Equation

 We compare the solution of to the solution of the same equation where f is replaced by a “concentrated” source . As a result we derive some estimates on the solution in spatial norm, locally uniformly in t, with respect to the norm of for any integer . In the case we obtain a critical inequality relating the norm of to an exponential norm of u. (Received 1 September 2000; in revised form 17 January 2001)