Polynomial-time approximation schemes for circle and other packing problems

DOI10.1007/S00453-015-0052-4zbMATH Open1385.68053arXiv1412.4709OpenAlexW2141627423MaRDI QIDQ329299FDOQ329299

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)

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.

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

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

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)

Cites Work

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

Cited In (16)

• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Split packing: algorithms for packing circles with optimal worst-case density
• Polynomial-time approximation schemes for circle packing problems
• Efficient Approximations for the Online Dispersion Problem
• Computational aspects of packing problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Placing your coins on a shelf
• Polynomial-time approximation schemes for packing and piercing fat objects
• Placing your coins on a shelf
• Techniques and results on approximation algorithms for packing circles
• Two-dimensional knapsack for circles
• Online circle and sphere packing
• Split packing: an algorithm for packing circles with optimal worst-case density
• 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)