A Framework for Efficient Approximation Schemes on Geometric Packing Problems of $d$-dimensional Fat Objects

We investigate approximation algorithms for several fundamental optimization problems on geometric packing. The geometric objects considered are very generic, namely $d$-dimensional convex fat objects. Our main contribution is a versatile framework for designing efficient approximation schemes for classic geometric packing problems. The framework effectively addresses problems such as the multiple knapsack, bin packing, multiple strip packing, and multiple minimum container problems. Furthermore, the framework handles additional problem features, including item multiplicity, item rotation, and additional constraints on the items commonly encountered in packing contexts. The core of our framework lies in formulating the problems as integer programs with a nearly decomposable structure. This approach enables us to obtain well-behaved fractional solutions, which can then be efficiently rounded. By modeling the problems in this manner, our framework offers significant flexibility, allowing it to address a wide range of problems and incorporate additional features. To the best of our knowledge, prior to this work, the known results on approximation algorithms for packing problems were either highly fixed for one problem or restricted to one class of objects, mainly polygons and hypercubes. In this sense, our framework is the first result with a general toolbox flavor in the context of approximation algorithms for geometric packing problems. Thus, we believe that our technique is of independent interest, being possible to inspire further work on geometric packing.

• Publication year

  2024

• Venue

  Unknown venue

• Publication date

  2024-04-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2405.00246
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects

  2024cited by this paper
• Proportional Packing of Circles in a Circular Container

  2023cited by this paper
• Approximation Schemes Under Resource Augmentation for Knapsack and Packing Problems of Hyperspheres and Other Shapes

  2023cited by this paper
• Techniques and results on approximation algorithms for packing circles

  2022cited by this paper
• A PTAS for Packing Hypercubes into a Knapsack

  2022influential reference
• Circle packing in regular polygons

  2022cited by this paper
• Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More

  2021cited by this paper
• On the Two-Dimensional Knapsack Problem for Convex Polygons

  2020cited by this paper
• A local search-based method for sphere packing problems

  2019cited by this paper
• A matheuristic approach with nonlinear subproblems for large-scale packing of ellipsoids

  2019cited by this paper
• Two-Dimensional Knapsack for Circles

  2018cited by this paper
• Approximation and online algorithms for multidimensional bin packing: A survey

  2017cited by this paper
• Approximating Geometric Knapsack via L-Packings

  2017cited by this paper
• The sphere packing problem in dimension 24

  2016cited by this paper
• Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container

  2016cited by this paper
• Packing ellipsoids by nonlinear optimization

  2015cited by this paper
• Hard sphere packings within cylinders.

  2015cited by this paper
• Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

  2014influential reference
• Improved Approximation Algorithm for Two-Dimensional Bin Packing

  2014cited by this paper
• Bin packing approximation algorithms: Survey and classification

  2013cited by this paper
• Packing circles within ellipses

  2013cited by this paper
• Circle Packing for Origami Design Is Hard

  2010cited by this paper
• A beam search algorithm for the circular packing problem

  2009cited by this paper
• A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies

  2009cited by this paper
• Approximation algorithms for orthogonal packing problems for hypercubes

  2009influential reference
• Minimizing the object dimensions in circle and sphere packing problems

  2008cited by this paper
• A note on the approximability of cutting stock problems

  2007influential reference
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes

  2006cited by this paper
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem

  2000cited by this paper
• A Formulation of the Kepler Conjecture

  1998cited by this paper
• Packing Squares into a Square

  1990influential reference
• Integer Programming with a Fixed Number of Variables

  1983influential reference
• Optimal Tile Salvage.

  1981cited by this paper
• Bin packing can be solved within 1 + ε in linear time

  1981cited by this paper
• Optimal Packing and Covering in the Plane are NP-Complete

  1981cited by this paper
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms

  1980cited by this paper
• On packing of squares and cubes

  1968influential reference

• No citing papers are available for this paper.