Polynomiality for Bin Packing with a Constant Number of Item Types
© 2020 ACM. 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,...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/133285 |
| _version_ | 1826193734544392192 |
|---|---|
| author | Goemans, Michel X Rothvoss, Thomas |
| author_facet | Goemans, Michel X Rothvoss, Thomas |
| author_sort | Goemans, Michel X |
| collection | MIT |
| description | © 2020 ACM. 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 ≥ 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. |
| first_indexed | 2024-09-23T09:44:05Z |
| format | Article |
| id | mit-1721.1/133285 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:44:05Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1332852021-10-28T04:41:07Z Polynomiality for Bin Packing with a Constant Number of Item Types Goemans, Michel X Rothvoss, Thomas © 2020 ACM. 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 ≥ 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. 2021-10-27T19:51:55Z 2021-10-27T19:51:55Z 2020 2021-05-20T12:04:07Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/133285 en 10.1145/3421750 Journal of the ACM Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Goemans, Michel X Rothvoss, Thomas Polynomiality for Bin Packing with a Constant Number of Item Types |
| title | Polynomiality for Bin Packing with a Constant Number of Item Types |
| title_full | Polynomiality for Bin Packing with a Constant Number of Item Types |
| title_fullStr | Polynomiality for Bin Packing with a Constant Number of Item Types |
| title_full_unstemmed | Polynomiality for Bin Packing with a Constant Number of Item Types |
| title_short | Polynomiality for Bin Packing with a Constant Number of Item Types |
| title_sort | polynomiality for bin packing with a constant number of item types |
| url | https://hdl.handle.net/1721.1/133285 |
| work_keys_str_mv | AT goemansmichelx polynomialityforbinpackingwithaconstantnumberofitemtypes AT rothvossthomas polynomialityforbinpackingwithaconstantnumberofitemtypes |