Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

Flávio Keidi Miyazawa, Lehilton L. C. Pedrosa, Rafael Crivellari Saliba Schouery, Maxim Sviridenko, Yoshiko Wakabayashi

Abstract

We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height $1+\gamma$, for some arbitrarily small number $\gamma > 0$. Our algorithm is polynomial on $\log 1/\gamma$, and thus $\gamma$ is part of the problem input. For the special case that $\gamma$ is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height $1+\gamma$ using no more than the number of bins in an optimal packing. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. These are the first approximation and resource augmentation schemes for these problems. Our algorithm is based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the $L_p$-norm.

Introduction

Packing problems are a staple of computer science and operations research, yet a significant gap has long existed between the treatment of rectangular and circular items. While efficient algorithms exist for packing rectangles into bins, circles present unique geometric challenges. Because circles do not possess straight edges, they do not "stack" neatly, leading to non-linear constraints and optimal coordinates that are frequently irrational.

In this work, Miyazawa et al. present the first Asymptotic Polynomial-Time Approximation Scheme (APTAS) for circle bin packing and circle strip packing. By synthesizing techniques from algebraic geometry with recursive partitioning, the authors provide a theoretical framework that guarantees near-optimal solutions for these historically difficult problems.

The Challenge of Curvature and Irrationality

The Circle Bin Packing Problem seeks the minimum number of unit square bins required to contain a set of circles with varying radii. Similarly, the Circle Strip Packing Problem aims to minimize the total height of a fixed-width strip containing the circles.

Unlike rectangle packing, which relies on linear constraints, circles involve quadratic constraints: for two circles $i$ and $j$ to avoid overlap, the distance between their centers must satisfy $\sqrt{(x_i-x_j)^2 + (y_i-y_j)^2} \ge r_i + r_j$. This introduces two primary hurdles:

  1. NP-Hardness: Determining if a small set of circles can fit within a single square is itself an NP-hard problem.
  2. Irrationality: The optimal coordinates for circle centers are often irrational numbers. This makes it impossible to represent an exact optimal solution on standard digital hardware using rational numbers.

Methodological Innovations

The proposed algorithm overcomes these hurdles through three core pillars:

1. Algebraic Quantifier Elimination

To manage "large" circles—defined as those where only a constant number can fit within a single bin—the authors treat the packing problem as a system of polynomial inequalities. Rather than using traditional discretization methods (which attempt to snap items to a grid), they employ algorithms from real algebraic geometry, specifically quantifier elimination. This allows the algorithm to handle the "curvy" nature of circles with high precision, as the complexity depends on $\log(1/\gamma)$ rather than the linear $1/\gamma$ required by grid-based searches.

2. Iterative Separation of Scales

The algorithm employs a recursive strategy to group circles into classes based on exponentially decreasing radii. By identifying a "buffer" class of circles with negligible total area, the algorithm can pack these items greedily without impacting overall efficiency. This creates a size gap that allows larger circles to be treated as fixed obstacles while smaller circles are handled as a fluid-like mass, simplifying the remaining packing steps.

3. Resource Augmentation and Sub-binning

To address the irrationality of optimal placements, the authors utilize Resource Augmentation. They allow the bins to be slightly taller (height $1+\gamma$). This infinitesimal increase in space provides the necessary "wiggle room" to shift circles from their ideal (possibly irrational) coordinates to nearby rational coordinates without causing overlaps. A "Lifting Lemma" proves that if circles overlap slightly in an approximate packing, they can be shifted vertically in a slightly taller bin to resolve all intersections.

Key Results and Extensions

The algorithm provides the following guarantees:

  • Circle Bin Packing: A packing using at most $(1+\epsilon)OPT + O(1)$ bins of size $1 \times (1+\gamma)$.
  • Circle Strip Packing: A packing with height at most $(1+\epsilon)OPT + O(1/\epsilon)$.
  • Resource Augmentation: If the height increase $\epsilon$ is a fixed constant, the algorithm achieves a packing using no more bins than the optimal packing would use in non-augmented bins ($A_\epsilon(C) \le OPT(C)$).

Furthermore, the framework is highly generalizable. The authors demonstrate that the logic extends to $d$-dimensional spheres (under various $L_p$ norms) and bins of diverse shapes, provided the shapes can be described as semi-algebraic sets.

Conclusion

This research marks a significant milestone in combinatorial optimization by providing the first APTAS for circle packing. While the "asymptotic" nature of the guarantee means the $(1+\epsilon)$ factor is most effective for large instances, the work establishes a rigorous foundation for handling non-linear packing constraints. Future work remains to determine if rational packings for circles with rational radii are always possible without resource augmentation, or if the $1+\gamma$ height requirement is a fundamental geometric necessity.

Summary updated

Abstract

We give an asymptotic approximation scheme (APTAS) for the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height $1+\gamma$, for some arbitrarily small number $\gamma > 0$. Our algorithm is polynomial on $\log 1/\gamma$, and thus $\gamma$ is part of the problem input. For the special case that $\gamma$ is constant, we give a (one dimensional) resource augmentation scheme, that is, we obtain a packing into bins of unit width and height $1+\gamma$ using no more than the number of bins in an optimal packing. Additionally, we obtain an APTAS for the circle strip packing problem, whose goal is to pack a set of circles into a strip of unit width and minimum height. These are the first approximation and resource augmentation schemes for these problems. Our algorithm is based on novel ideas of iteratively separating small and large items, and may be extended to a wide range of packing problems that satisfy certain conditions. These extensions comprise problems with different kinds of items, such as regular polygons, or with bins of different shapes, such as circles and spheres. As an example, we obtain APTAS's for the problems of packing d-dimensional spheres into hypercubes under the $L_p$-norm.
BibTeX
@inproceedings{miyazawa2016polynomial,
  author = {Flávio Keidi Miyazawa and Lehilton L. C. Pedrosa and Rafael Crivellari Saliba Schouery and Maxim Sviridenko and Yoshiko Wakabayashi},
  title = {{Polynomial-Time Approximation Schemes for Circle and Other Packing Problems}},
  booktitle = {Algorithmica},
  year = {2016},
  url = {https://openreview.net/forum?id=G1SdMkXVD6B},
}

Loading related content...

Figure