{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T02:27:41Z","timestamp":1673404061840},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T00:00:00Z","timestamp":1604707200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006435","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1115849"]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher"},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher"},{"DOI":"10.13039\/100007297","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-11-1-0053"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"\n We consider the bin packing problem with\n d<\/jats:italic>\n different item sizes\n s<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n and item multiplicities\n a<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n , where all numbers are given in binary encoding. This problem formulation is also known as the\n one-dimensional cutting stock problem<\/jats:italic>\n . In this work, we provide an algorithm that, for constant\n d<\/jats:italic>\n , solves bin packing in polynomial time. This was an open problem for all\n d\\ge 3<\/jats:italic>\n . In fact, for constant\n d<\/jats:italic>\n our algorithm solves the following problem in polynomial time: Given two\n d<\/jats:italic>\n -dimensional polytopes\n P<\/jats:italic>\n and\n Q<\/jats:italic>\n , find the smallest number of integer points in\n P<\/jats:italic>\n whose sum lies in\n Q<\/jats:italic>\n . Our approach also applies to\n high multiplicity<\/jats:italic>\n 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.\n <\/jats:p>","DOI":"10.1145\/3421750","type":"journal-article","created":{"date-parts":[[2020,11,8]],"date-time":"2020-11-08T05:12:45Z","timestamp":1604812365000},"page":"1-21","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Polynomiality for Bin Packing with a Constant Number of Item Types"],"prefix":"10.1145","volume":"67","author":[{"given":"Michel X.","family":"Goemans","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Thomas","family":"Rothvoss","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,11,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204716"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1943.11991447"},{"key":"#cr-split#-e_1_2_1_3_1.1","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe. 2014. Convex Optimization. Cambridge University Press. DOI:https:\/\/doi.org\/10.1017\/CBO9780511804441 10.1017\/CBO9780511804441","DOI":"10.1017\/CBO9780511804441"},{"key":"#cr-split#-e_1_2_1_3_1.2","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe. 2014. Convex Optimization. Cambridge University Press. DOI:https:\/\/doi.org\/10.1017\/CBO9780511804441","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01191202"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the IFIP Congress. 807--813","author":"Dertouzos M. L.","year":"1974","unstructured":"M. L. Dertouzos . 1974 . Control robotics: The procedural control of physical processes . In Proceedings of the IFIP Congress. 807--813 . M. L. Dertouzos. 1974. Control robotics: The procedural control of physical processes. In Proceedings of the IFIP Congress. 807--813."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.09.008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113613.3114007"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.06.016"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.6.849"},{"key":"e_1_2_1_10_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Company New York NY. M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Company New York NY."},{"key":"e_1_2_1_11_1","unstructured":"M. Hartmann. 1988. Cutting Planes and the Complexity of the Integer Hull. Retrieved from http:\/\/hdl.handle.net\/1813\/8702. M. Hartmann. 1988. Cutting Planes and the Complexity of the Integer Hull. Retrieved from http:\/\/hdl.handle.net\/1813\/8702."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Hoberg R.","year":"1974","unstructured":"R. Hoberg and T. Rothvoss . 2017. A logarithmic additive integrality gap for bin packing . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) . 2616--2625. DOI:https:\/\/doi.org\/10.1137\/1.978161 1974 782.172 10.1137\/1.9781611974782.172 R. Hoberg and T. Rothvoss. 2017. A logarithmic additive integrality gap for bin packing. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). 2616--2625. DOI:https:\/\/doi.org\/10.1137\/1.9781611974782.172"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.4.648"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Jansen K.","unstructured":"K. Jansen and K. Klein . 2017. About the structure of the integer cone and its application to bin packing . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 1571--1581. K. Jansen and K. Klein. 2017. About the structure of the integer cone and its application to bin packing. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). Society for Industrial and Applied Mathematics, Philadelphia, PA, 1571--1581."},{"key":"e_1_2_1_15_1","volume-title":"Studies and Essays Presented to R. Courant on his 60th Birthday","author":"John F.","year":"1948","unstructured":"F. John . 1948. Extremum problems with inequalities as subsidiary conditions . In Studies and Essays Presented to R. Courant on his 60th Birthday , January 8, 1948 . Interscience Publishers, Inc. , New York, NY , 187--204. F. John. 1948. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948. Interscience Publishers, Inc., New York, NY, 187--204."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90052-E"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.02.009"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201910)","author":"Jansen K.","unstructured":"K. Jansen and R. Solis-Oba . 2010. An OPT + 1 algorithm for the cutting stock problem with constant number of object lengths . In Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201910) , Friedrich Eisenbrand and F. Bruce Shepherd (Eds.). 438--449. K. Jansen and R. Solis-Oba. 2010. An OPT + 1 algorithm for the cutting stock problem with constant number of object lengths. In Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201910), Friedrich Eisenbrand and F. Bruce Shepherd (Eds.). 438--449."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE","author":"Karmarkar N.","unstructured":"N. Karmarkar and R. M. Karp . 1982. An efficient approximation scheme for the one-dimensional bin-packing problem . In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE , New York, 312--320. N. Karmarkar and R. M. Karp. 1982. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE, New York, 312--320."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"B. Korte and J. Vygen. 2002. Combinatorial Optimization\u2014Theory and Algorithms (2nd ed.). Springer-Verlag. B. Korte and J. Vygen. 2002. Combinatorial Optimization\u2014Theory and Algorithms (2nd ed.). Springer-Verlag.","DOI":"10.1007\/978-3-662-21711-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997)","author":"McCormick S. T.","year":"1997","unstructured":"S. T. McCormick , S. R. Smallwood , and F. C. R. Spieksma . 1997 . Polynomial algorithms for multiprocessor scheduling with a small number of job lengths . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997) . 509--517. S. T. McCormick, S. R. Smallwood, and F. C. R. Spieksma. 1997. Polynomial algorithms for multiprocessor scheduling with a small number of job lengths. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997). 509--517."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2780413.2780416"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.11"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0049416"},{"key":"e_1_2_1_27_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","unstructured":"A. Schrijver . 1999. Theory of Linear and Integer Programming . Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley . A. Schrijver. 1999. Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3421750","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3421750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T18:33:13Z","timestamp":1672597993000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3421750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,7]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3421750"],"URL":"http:\/\/dx.doi.org\/10.1145\/3421750","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2020,11,7]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}