About the Structure of the Integer Cone and Its Application to Bin Packing

DOI10.1287/MOOR.2019.1040MaRDI QIDQ3387933zbMATH OpenOpenAlexFDO

Authors Kim-Manuel Klein, Klaus Jansen

Publication date 8 January 2021

Published in Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

integer programmingbin packingstructural properties

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Integer programming (90C10)

Abstract: We consider the bin packing problem with $d$ different item sizes and revisit the structure theorem given by Goemans and Rothvoss [6] about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time $|V{|}^{2^{O(d)}}cdotenc(I{)}^{O(1)}$, where $V$ is the set of vertices of the integer knapsack polytope and $enc(I)$ is the encoding length of the bin packing instance. The algorithm is fixed parameter tractable, parameterized by the number of vertices of the integer knapsack polytope $|V|$. This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure, i.e. has a small number of vertices. Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound.

Recommendations

• About the structure of the integer cone and its application to bin packing
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• A tight lower bound for optimal bin packing
• Approximate packing: integer programming models, valid inequalities and nesting
• Some inequalities for bin packing
• On a generalized bin-packing problem
• A classification scheme for bin packing theory
• Bin packing with ``largest in bottom constraint: tighter bounds and generalizations
• An asymptotic approximation scheme for the concave cost bin packing problem
• On a combinatorial structure of the problems of optimal packing of geometric objects

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 3315310 (Why is no real title available?)
• A logarithmic additive integrality gap for bin packing
• A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths
• Carathéodory bounds for integer cones
• Diophantine approximations and integer points of cones
• Friendly bin packing instances without integer round-up property
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• New Hardness Results for Diophantine Approximation
• On integer points in polyhedra
• Polynomiality for bin packing with a constant number of item types
• The vertices of the knapsack polytope
• Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem

Cited in

(4)

• Parameterized complexity of configuration integer programs
• About the structure of the integer cone and its application to bin packing
• Fair and efficient allocation with few agent types, few item types, or small value levels
• The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers

This page was built for publication: About the Structure of the Integer Cone and Its Application to Bin Packing

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