Polynomial-time approximation schemes for circle and other packing problems
From MaRDI portal
Publication:329299
DOI10.1007/s00453-015-0052-4zbMath1385.68053arXiv1412.4709OpenAlexW2141627423MaRDI QIDQ329299
Rafael C. S. Schouery, Lehilton L. C. Pedrosa, Flávio K. Miyazawa, Yoshiko Wakabayashi, M. I. 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
algebraic algorithmssphere packingasymptotic approximation schemecircle bin packingcircle strip packingresource augmentation scheme
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
Online circle and sphere packing ⋮ Efficient Approximations for the Online Dispersion Problem ⋮ Techniques and results on approximation algorithms for packing circles
Cites Work
- Unnamed Item
- A literature review on circle and sphere packing problems: models and methodologies
- An algorithm for the three-dimensional packing problem with asymptotic performance analysis
- New approaches to circle packing in a square. With program codes.
- 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
- Bin packing can be solved within 1+epsilon in linear time
- Multidimensional cube packing
- Absolute approximation ratios for packing rectangles into bins
- An improved typology of cutting and packing problems
- New and improved results for packing identical unitary radius circles within triangles, rectangles and strips
- A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
- A Harmonic Algorithm for the 3D Strip Packing Problem
- Integer Programming with a Fixed Number of Variables
- Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
- On Three-Dimensional Packing
- An asymptotic approximation algorithm for 3D-strip packing
- 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
- Orthogonal Packings in Two Dimensions
- On Packing Two-Dimensional Bins
- A Strip-Packing Algorithm with Absolute Performance Bound 2
- On the combinatorial and algebraic complexity of quantifier elimination
- A (5/3 + ε)-Approximation for Strip Packing
- Improved Approximation Algorithm for Two-Dimensional Bin Packing
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- On packing of squares and cubes
- New Approximability Results for Two-Dimensional Bin Packing
- Algorithms - ESA 2003
- Algorithms in real algebraic geometry
