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

TL;DR

This paper introduces the first polynomial-time approximation schemes (APTAS) for packing circles into square bins and for packing circles into a strip. The authors achieve this by novelly separating "large" and "small" circles and using algebraic quantifier elimination, extending their approach to various packing problems including spheres in higher dimensions.

What Problem Does This Paper Address?

The paper tackles the classic problem of packing circles into bins (either square or a long strip) to minimize the number of bins used. This is a fundamental problem in areas like logistics, manufacturing, and resource allocation. While previous work has focused on packing simpler shapes like rectangles, or used heuristics for circles, this paper aims to provide provable, efficient approximation algorithms for circle packing. A key challenge is that exact solutions are NP-hard, and previous approximation algorithms for circles were lacking. The authors also address the practical issue of obtaining rational coordinates for circle placements, which often requires slight "fudging" of bin sizes.

Methods

The core of the paper's methodology lies in a clever combination of techniques:

  • Algebraic Quantifier Elimination: For deciding if a set of circles can fit into a bin, the authors formulate the problem as a system of polynomial inequalities. They then leverage advanced algebraic algorithms (specifically, those for quantifier elimination) to determine feasibility and find approximate placements. This is a novel approach for packing problems.
  • Iterative Separation of "Large" and "Small" Items: The algorithm dynamically categorizes circles as "large" or "small" in different stages. This allows for a structured approach where large items are handled first, creating a framework for packing smaller items into the remaining space.
  • Augmented Bins: To handle the irrational coordinates produced by algebraic methods, the authors introduce "augmented" bins (slightly larger than standard bins). This allows for approximate packings to be converted into valid, non-overlapping packings. The dependency on the augmentation parameter is logarithmic, which is efficient.
  • Resource Augmentation: For a specific case (constant bin enlargement), they show a packing that uses no more bins than an optimal packing without this enlargement.
  • Generalization: The framework is designed to be extensible to other shapes (polygons, spheres) and bin types (hyperrectangles, spheres) by adapting the algebraic formulation.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and does not present experimental evaluations on specific datasets.

Key Insights and Ideas

  • Algebraic Geometry for Packing: The most significant insight is the successful application of algebraic quantifier elimination to solve geometric packing decision problems. This bypasses combinatorial brute-force methods and provides a more robust theoretical foundation.
  • Dynamic Item Sizing: The idea of treating items as "large" or "small" dynamically, rather than statically, is crucial for handling the complex interactions between circles of varying sizes.
  • Augmented Bins as a Bridge: Using slightly larger bins is a practical and theoretically sound way to bridge the gap between exact geometric constraints and the approximate solutions from algebraic solvers.
  • Unified Framework: The algorithm's structure suggests a general approach applicable to a broad class of packing problems, not just circles.

Key Results

  • APTAS for Circle Bin Packing: The paper provides an Asymptotic Polynomial-Time Approximation Scheme (APTAS) for packing circles into unit square bins. This means for any desired accuracy $\epsilon > 0$, the algorithm finds a packing using at most $(1+\epsilon)$ times the optimal number of bins, plus a small constant. The runtime is polynomial in $\log(1/\gamma)$, where $\gamma$ is a parameter related to bin augmentation.
  • APTAS for Circle Strip Packing: An APTAS is also presented for packing circles into a strip of unit width, minimizing the strip's height.
  • Resource Augmentation Scheme: For a constant bin enlargement, they achieve a packing that uses no more bins than the optimal solution without enlargement.
  • Generalizations: The framework is shown to extend to packing d-dimensional Lp-norm spheres into hypercubes and other related problems.

Limitations and Future Work

  • Rational Coordinates: While the algorithms provide theoretical guarantees, the direct output of the algebraic methods can be irrational coordinates. The paper addresses this by using augmented bins and approximate rational solutions, but leaves open the question of whether a rational solution can always be obtained for rational inputs without augmentation.
  • Computational Complexity: While polynomial in theory, the practical performance of algebraic quantifier elimination algorithms can be high, especially for many variables. The paper acknowledges that the complexity can be exponential in the number of variables, though it is polynomial in the input size and logarithmic in the augmentation parameter.
  • Practical Implementation: The paper focuses on theoretical guarantees. Further research would involve implementing these algorithms and testing their practical performance against existing heuristics.
  • More General Items/Bins: The paper suggests extensions to items of mixed shapes and bins of arbitrary semi-algebraic shapes, which would be a natural next step.

Summary updated

Abstract

We consider 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 $$ 1 + γ , for some arbitrarily small number $$\gamma > 0$$ γ > 0 . For this problem, we obtain an asymptotic approximation scheme (APTAS) that is polynomial on $$\log 1/\gamma $$ log 1 / γ , and thus $$\gamma $$ γ may be given as 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 $$ 1 + γ using no more than the number of bins in an optimal packing without resource augmentation. 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. Our algorithms are the first approximation schemes for circle packing problems, and are 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$$ 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},
}
Figure