{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T06:22:58Z","timestamp":1781072578349,"version":"3.54.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["185030"],"award-info":[{"award-number":["185030"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>\n            We consider integer programming problems in standard form max {\n            <jats:italic>c<\/jats:italic>\n            <jats:sup>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>x<\/jats:italic>\n            :\n            <jats:italic>Ax<\/jats:italic>\n            =\n            <jats:italic>b<\/jats:italic>\n            ,\n            <jats:italic>x<\/jats:italic>\n            \u2a7e 0,\n            <jats:italic>x<\/jats:italic>\n            \u2208 Z\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            } where\n            <jats:italic>A<\/jats:italic>\n            \u2208 Z\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n              \u00d7\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ,\n            <jats:italic>b<\/jats:italic>\n            \u2208 Z\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n            <\/jats:sup>\n            , and\n            <jats:italic>c<\/jats:italic>\n            \u2208 Z\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            . We show that such an integer program can be solved in time (\n            <jats:italic>m<\/jats:italic>\n            \u22c5 \u0394)\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>m<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u22c5 \\Vert b\\Vert\n            <jats:sub>\u221e<\/jats:sub>\n            <jats:sup>2<\/jats:sup>\n            , where \u0394 is an upper bound on each absolute value of an entry in\n            <jats:italic>A<\/jats:italic>\n            . This improves upon the longstanding best bound of Papadimitriou [27] of (\n            <jats:italic>m<\/jats:italic>\n            \u22c5 \u0394)\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>m<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              )\n            <\/jats:sup>\n            , where in addition, the absolute values of the entries of\n            <jats:italic>b<\/jats:italic>\n            also need to be bounded by \u0394. Our result relies on a lemma of Steinitz that states that a set of vectors in R\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n            <\/jats:sup>\n            that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by\n            <jats:italic>m<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We also use the Steinitz lemma to show that the \u2113\n            <jats:sub>1<\/jats:sub>\n            -distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by\n            <jats:italic>m<\/jats:italic>\n            \u22c5 (2,\n            <jats:italic>m<\/jats:italic>\n            \u22c5 \u0394 +1)\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n            <\/jats:sup>\n            . Here \u0394 is again an upper bound on the absolute values of the entries of\n            <jats:italic>A<\/jats:italic>\n            . The novel strength of our bound is that it is independent of\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.<\/jats:p>","DOI":"10.1145\/3340322","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T21:16:57Z","timestamp":1573852617000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":48,"title":["Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma"],"prefix":"10.1145","volume":"16","author":[{"given":"Friedrich","family":"Eisenbrand","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Weismantel","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,11,15]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"A. V. Aho J. E. Hopcroft and J. D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reaing.  A. V. Aho J. E. Hopcroft and J. D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reaing."},{"key":"e_1_2_1_2_1","volume-title":"International Conference on Integer Programming and Combinatorial Optimization. Springer, 25--38","author":"Aliev I.","unstructured":"I. Aliev , M. Henk , and T. Oertel . 2017. Integrality gaps of integer knapsack problems . In International Conference on Integer Programming and Combinatorial Optimization. Springer, 25--38 . I. Aliev, M. Henk, and T. Oertel. 2017. Integrality gaps of integer knapsack problems. In International Conference on Integer Programming and Combinatorial Optimization. Springer, 25--38."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/294762.294765"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20373"},{"key":"e_1_2_1_5_1","volume-title":"IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Bansal N.","unstructured":"N. Bansal , D. Dadush , and S. Garg . 2016. An algorithm for Koml\u00f3s conjecture matching Banaszczyk\u2019s bound . In IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916) . IEEE, 788--799. N. Bansal, D. Dadush, and S. Garg. 2016. An algorithm for Koml\u00f3s conjecture matching Banaszczyk\u2019s bound. In IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916). IEEE, 788--799."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 914--926","author":"Bansal N.","unstructured":"N. Bansal and S. Garg . 2017. Algorithmic discrepancy beyond partial coloring . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 914--926 . N. Bansal and S. Garg. 2017. Algorithmic discrepancy beyond partial coloring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 914--926."},{"key":"e_1_2_1_7_1","volume-title":"Building Bridges","author":"B\u00e1r\u00e1ny I.","unstructured":"I. B\u00e1r\u00e1ny . 2008. On the power of linear dependencies . In Building Bridges . Springer , 31--45. I. B\u00e1r\u00e1ny. 2008. On the power of linear dependencies. In Building Bridges. Springer, 31--45."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90022-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1976-0396605-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0474-y"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582230"},{"key":"e_1_2_1_12_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms (2nd ed.). MIT Press Cambridge MA.  T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms (2nd ed.). MIT Press Cambridge MA."},{"key":"e_1_2_1_13_1","unstructured":"D. N. Dadush. 2012. Integer Programming Lattice Algorithms and Deterministic Volume Estimation. Georgia Institute of Technology.  D. N. Dadush. 2012. Integer Programming Lattice Algorithms and Deterministic Volume Estimation. Georgia Institute of Technology."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0384-4"},{"key":"e_1_2_1_15_1","unstructured":"F. V. Fomin F. Panolan M. Ramanujan and S. Saurabh. 2016. Fine-grained complexity of integer programming: The case of bounded branch-width and rank. arXiv preprint arXiv:1607.05342 (2016).  F. V. Fomin F. Panolan M. Ramanujan and S. Saurabh. 2016. Fine-grained complexity of integer programming: The case of bounded branch-width and rank. arXiv preprint arXiv:1607.05342 (2016)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01086559"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/090749451"},{"key":"e_1_2_1_20_1","unstructured":"K.\n      Jansen K.-M.\n      Klein and \n      J.\n      Verschae\n  . \n  2016\n  . Closing the gap for makespan scheduling via sparsification techniques. In 43rd International Colloquium on Automata Languages and Programming (ICALP \u201916) volume \n  55\n   of \n  LIPIcs\n  . Schloss Dagstuhl-Leibniz-Zentrum fuer \n  Informatik\n  .  K. Jansen K.-M. Klein and J. Verschae. 2016. Closing the gap for makespan scheduling via sparsification techniques. In 43rd International Colloquium on Automata Languages and Programming (ICALP \u201916) volume 55 of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_21_1","volume-title":"10th Innovations in Theoretical Computer Science Conference (ITCS\u201919)","author":"Jansen K.","unstructured":"K. Jansen and L. Rohwedder . 2018. On integer programming and convolution . In 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. K. Jansen and L. Rohwedder. 2018. On integer programming and convolution. In 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2875343.2875346"},{"key":"e_1_2_1_23_1","unstructured":"D. Knop M. Pilipczuk and M. Wrochna. 2018. Tight complexity lower bounds for integer linear programming with few constraints. arXiv preprint arXiv:1811.01296 (2018).  D. Knop M. Pilipczuk and M. Wrochna. 2018. Tight complexity lower bounds for integer linear programming with few constraints. arXiv preprint arXiv:1811.01296 (2018)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_25_1","first-page":"11","article-title":"Structure and hardness in p (Dagstuhl seminar 16451)","volume":"6","author":"Lewenstein M.","year":"2017","unstructured":"M. Lewenstein , S. Pettie , and V. Vassilevska Williams . 2017 . Structure and hardness in p (Dagstuhl seminar 16451) . In Dagstuhl Reports , volume 6 : 11 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. M. Lewenstein, S. Pettie, and V. Vassilevska Williams. 2017. Structure and hardness in p (Dagstuhl seminar 16451). In Dagstuhl Reports, volume 6:11. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","journal-title":"Dagstuhl Reports"},{"key":"e_1_2_1_26_1","volume-title":"Geometric Discrepancy: An Illustrated Guide","author":"Matousek J.","year":"2009","unstructured":"J. Matousek . 2009 . Geometric Discrepancy: An Illustrated Guide , Vol. 18 . Springer Science 8 Business Media. J. Matousek. 2009. Geometric Discrepancy: An Illustrated Guide, Vol. 18. Springer Science 8 Business Media."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322287"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050042"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0381"},{"key":"e_1_2_1_30_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","unstructured":"A. Schrijver . 1986. Theory of Linear and Integer Programming . John Wiley . A. Schrijver. 1986. Theory of Linear and Integer Programming. John Wiley."},{"key":"e_1_2_1_31_1","first-page":"66","article-title":"Approximate solution of some problems of scheduling theory","volume":"32","author":"Sevast\u2019janov S.","year":"1978","unstructured":"S. Sevast\u2019janov . 1978 . Approximate solution of some problems of scheduling theory . Metody Diskretnogi Analiza 32 (1978), 66 -- 75 . S. Sevast\u2019janov. 1978. Approximate solution of some problems of scheduling theory. Metody Diskretnogi Analiza 32 (1978), 66--75.","journal-title":"Metody Diskretnogi Analiza"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00240-J"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1913.143.128"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2009.05.003"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340322","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:32Z","timestamp":1750268972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,15]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3340322"],"URL":"https:\/\/doi.org\/10.1145\/3340322","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,15]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}