{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:08:13Z","timestamp":1758265693304,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-11-1-0053"],"award-info":[{"award-number":["N00014-11-1-0053"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0829878"],"award-info":[{"award-number":["CCF-0829878"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["PD 104386"],"award-info":[{"award-number":["PD 104386"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Feodor Lynen program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:p>\n            A well-studied special case of\n            <jats:italic>bin packing<\/jats:italic>\n            is the\n            <jats:italic>3-partition problem<\/jats:italic>\n            , where\n            <jats:italic>n<\/jats:italic>\n            items of size &gt; 1\/4 have to be packed in a minimum number of bins of capacity one. The famous\n            <jats:italic>Karmarkar-Karp algorithm<\/jats:italic>\n            transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) additional bins.\n          <\/jats:p>\n          <jats:p>\n            The\n            <jats:italic>three-permutations-problem<\/jats:italic>\n            of Beck is the following. Given any three permutations on\n            <jats:italic>n<\/jats:italic>\n            symbols, color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols is roughly the same. The necessary difference is called the\n            <jats:italic>discrepancy<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>We establish a surprising connection between bin packing and Beck\u2019s problem: The additive integrality gap of the 3-partition linear programming relaxation can be bounded by the discrepancy of three permutations.<\/jats:p>\n          <jats:p>\n            This connection yields an alternative method to establish an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) bound on the additive integrality gap of the 3-partition. Conversely, making use of a recent example of three permutations, for which a discrepancy of \u03a9(log\n            <jats:italic>n<\/jats:italic>\n            ) is necessary, we prove the following: The\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) upper bound on the additive gap for bin packing with arbitrary item sizes cannot be improved by any technique that is based on rounding up items. This lower bound holds for a large class of algorithms including the Karmarkar-Karp procedure.\n          <\/jats:p>","DOI":"10.1145\/2483699.2483704","type":"journal-article","created":{"date-parts":[[2013,6,25]],"date-time":"2013-06-25T18:50:29Z","timestamp":1372186229000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Bin Packing via Discrepancy of Permutations"],"prefix":"10.1145","volume":"9","author":[{"given":"Friedrich","family":"Eisenbrand","sequence":"first","affiliation":[{"name":"EPFL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00f6m\u00f6t\u00f6r","family":"P\u00e1lv\u00f6lgyi","sequence":"additional","affiliation":[{"name":"E\u00f6tv\u00f6s Lor\u00e1nd University (ELTE)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199807)12:4%3C351::AID-RSA3%3E3.0.CO;2-S"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90022-6"},{"key":"e_1_2_1_4_1","first-page":"2","article-title":"Discrepancy theory","volume":"1","author":"Beck J.","year":"1995","journal-title":"Handbook of Combinatorics"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010208"},{"volume-title":"Proceedings of SODA. 1607--1614","author":"Charikar M.","key":"e_1_2_1_6_1"},{"volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"Diestel R.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2399256.2399257"},{"key":"e_1_2_1_9_1","first-page":"279","article-title":"The trim problem. Manage","volume":"3","author":"Eisemann K.","year":"1957","journal-title":"Sci."},{"volume-title":"Proceedings of SODA. 476--481","author":"Eisenbrand F.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579456"},{"key":"e_1_2_1_12_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York NY.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company New York NY."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.6.849"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_33"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.61"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(86)80041-5"},{"volume-title":"Geometric Discrepancy. An illustrated guide. Algorithms and Combinatorics","author":"Matou\u0161ek J.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","unstructured":"Newman A. and Nikolov A. 2011. A counterexample to Beck\u2019s conjecture on the discrepancy of three permutations. CoRR abs\/1104.2922.  Newman A. and Nikolov A. 2011. A counterexample to Beck\u2019s conjecture on the discrepancy of three permutations. CoRR abs\/1104.2922."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00047-8"},{"key":"e_1_2_1_23_1","unstructured":"Seb\u0151 A. and Shmonin G. 2009. Proof of the modified integer round-up conjecture for bin packing in dimension 7. Personal communication.  Seb\u0151 A. and Shmonin G. 2009. Proof of the modified integer round-up conjecture for bin packing in dimension 7. Personal communication."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1985-0784009-0"},{"key":"e_1_2_1_25_1","unstructured":"Spencer J. H. Srinivasan A. and Tetali P. The discrepancy of permutation families. www.cs.umd.edu\/~srin\/PDF\/disc-unpub.pdf.  Spencer J. H. Srinivasan A. and Tetali P. The discrepancy of permutation families. www.cs.umd.edu\/~srin\/PDF\/disc-unpub.pdf."},{"volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201997)","year":"1997","author":"Srinivasan A.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","unstructured":"Williamson D. 1998. Lecture notes on approximation algorithms. IBM Res. rep. http:\/\/legacy.orie.cornell.edu\/~dpw\/cornell.ps.  Williamson D. 1998. Lecture notes on approximation algorithms. IBM Res. rep. http:\/\/legacy.orie.cornell.edu\/~dpw\/cornell.ps."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2483699.2483704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2483699.2483704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:36Z","timestamp":1750277676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2483699.2483704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1145\/2483699.2483704"],"URL":"https:\/\/doi.org\/10.1145\/2483699.2483704","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}