Polynomial-time approximation schemes for circle and other packing problems

DOI10.1007/S00453-015-0052-4MaRDI QIDQ329299zbMATH OpenOpenAlexFDO

Authors Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Yoshiko Wakabayashi, Maxim Sviridenko

Publication date 21 October 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.4709

zbMATH Keywords

sphere packingalgebraic algorithmsasymptotic approximation schemecircle bin packingcircle strip packingresource augmentation scheme

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

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 $log1/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.

Recommendations

• Polynomial-time approximation schemes for circle packing problems
• Two-dimensional knapsack for circles
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Approximation schemes for multidimensional packing
• Techniques and results on approximation algorithms for packing circles

Cites work

• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• A 2.5 times optimal algorithm for packing in two dimensions
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A \((5/3 + \varepsilon )\)-approximation for strip packing
• A harmonic algorithm for the 3D strip packing problem
• A literature review on circle and sphere packing problems: models and methodologies
• A near-optimal solution to a two-dimensional cutting stock problem
• Absolute approximation ratios for packing rectangles into bins
• Algorithms in real algebraic geometry
• An algorithm for the three-dimensional packing problem with asymptotic performance analysis
• An asymptotic approximation algorithm for 3D-strip packing
• An improved typology of cutting and packing problems
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Bin packing can be solved within 1+epsilon in linear time
• Fast integer programming in fixed dimension
• Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
• Improved approximation algorithm for two-dimensional bin packing
• Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
• Integer Programming with a Fixed Number of Variables
• Multidimensional cube packing
• New and improved results for packing identical unitary radius circles within triangles, rectangles and strips
• New approaches to circle packing in a square. With program codes.
• New approximability results for two-dimensional bin packing
• On Packing Two-Dimensional Bins
• On Three-Dimensional Packing
• On packing of squares and cubes
• On the combinatorial and algebraic complexity of quantifier elimination
• Orthogonal Packings in Two Dimensions
• Packing different-sized circles into a rectangular container
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Solving systems of polynomial inequalities in subexponential time

Cited in

(16)

• Polynomial-time approximation schemes for packing and piercing fat objects
• Split packing: algorithms for packing circles with optimal worst-case density
• Two-dimensional knapsack for circles
• Placing your coins on a shelf
• Online circle and sphere packing
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Techniques and results on approximation algorithms for packing circles
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Computational aspects of packing problems
• scientific article; zbMATH DE number 1629820 (Why is no real title available?)
• Split packing: an algorithm for packing circles with optimal worst-case density
• scientific article; zbMATH DE number 824099 (Why is no real title available?)
• Polynomial-time approximation schemes for circle packing problems
• Placing your coins on a shelf
• Efficient approximations for the online dispersion problem
• PERM for solving circle packing problem

This page was built for publication: Polynomial-time approximation schemes for circle and other packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q329299)