Polynomiality for Bin Packing with a Constant Number of Item Types
- 7 November 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (6), 1-21
- https://doi.org/10.1145/3421750
Abstract
We consider the bin packing problem with d different item sizes si and item multiplicities ai, where all numbers are given in binary encoding. This problem formulation is also known as the one-dimensional cutting stock problem. In this work, we provide an algorithm that, for constant d, solves bin packing in polynomial time. This was an open problem for all d\ge 3. In fact, for constant d our algorithm solves the following problem in polynomial time: Given two d-dimensional polytopes P and Q, find the smallest number of integer points in P whose sum lies in Q. Our approach also applies to high multiplicity scheduling problems in which the number of copies of each job type is given in binary encoding and each type comes with certain parameters such as release dates, processing times, and deadlines. We show that a variety of high multiplicity scheduling problems can be solved in polynomial time if the number of job types is constant.Keywords
Funding Information
- National Science Foundation (1115849)
- David and Lucile Packard Foundation
- Alfred P. Sloan Foundation
- Office of Naval Research (N00014-11-1-0053)
This publication has 16 references indexed in Scilit:
- A simple OPT+1 algorithm for cutting stock under the modified integer round-up property assumptionInformation Processing Letters, 2011
- On the bin packing problem with a fixed number of object weightsEuropean Journal of Operational Research, 2007
- Carathéodory bounds for integer conesOperations Research Letters, 2006
- An asymptotically exact algorithm for the high-multiplicity bin packing problemMathematical Programming, 2005
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1992
- On integer points in polyhedra: A lower boundCombinatorica, 1992
- On integer points in polyhedraCombinatorica, 1992
- Strongly Polynomial Algorithms for the High Multiplicity Scheduling ProblemOperations Research, 1991
- Minkowski's Convex Body Theorem and Integer ProgrammingMathematics of Operations Research, 1987
- Integer Programming with a Fixed Number of VariablesMathematics of Operations Research, 1983