{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T18:38:40Z","timestamp":1773859120655,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"OP VVV MEYS","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["CUTACOMBS, PowAlgDo,TOTAL"],"award-info":[{"award-number":["CUTACOMBS, PowAlgDo,TOTAL"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["START"],"award-info":[{"award-number":["START"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/19"],"award-info":[{"award-number":["NI 369\/19"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>\n            We consider the standard ILP F\n            <jats:sc>easibility<\/jats:sc>\n            problem: given an integer linear program of the form {A\n            <jats:italic>x<\/jats:italic>\n            = b, x \u2a7e 0}, where\n            <jats:italic>A<\/jats:italic>\n            is an integer matrix with\n            <jats:italic>k<\/jats:italic>\n            rows and \u2113 columns, x is a vector of \u2113 variables, and b is a vector of\n            <jats:italic>k<\/jats:italic>\n            integers, we ask whether there exists x \u2208 N \u2113 that satisfies Ax = b. Each row of\n            <jats:italic>A<\/jats:italic>\n            specifies one linear\n            <jats:italic>constraint<\/jats:italic>\n            on x; our goal is to study the complexity of ILP F\n            <jats:sc>easibility<\/jats:sc>\n            when both\n            <jats:italic>k<\/jats:italic>\n            , the number of constraints, and \u2016A\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            , the largest absolute value of an entry in\n            <jats:italic>A<\/jats:italic>\n            , are small.\n          <\/jats:p>\n          <jats:p>\n            Papadimitriou was the first to give a fixed-parameter algorithm for ILP F\n            <jats:sc>easibility<\/jats:sc>\n            under parameterization by the number of constraints that runs in time ((\u2016A\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            + \u2016b\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            ) \u22c5\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              <jats:sup>2<\/jats:sup>\n              )\n            <\/jats:sup>\n            . This was very recently improved by Eisenbrand and Weismantel, who used the Steinitz lemma to design an algorithm with running time (\n            <jats:italic>k<\/jats:italic>\n            \u2016A\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u22c5 log \u2016b\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            , which was subsequently refined by Jansen and Rohwedder to\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>k<\/jats:italic>\n            \u2016A\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            )\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            \u22c5 log (\u2016 A\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            + \u2016b\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            ) \u22c5 log \u2016A\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            . We prove that for {0, 1}-matrices\n            <jats:italic>A<\/jats:italic>\n            , the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              log\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u22c5 (\u2113 + \u2016b\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            )\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            would contradict the exponential time hypothesis. This improves previous non-tight lower bounds of Fomin et al.\n          <\/jats:p>\n          <jats:p>\n            We then consider integer linear programs that may have many constraints, but they need to be structured in a \u201cshallow\u201d way. Precisely, we consider the parameter\n            <jats:italic>dual treedepth<\/jats:italic>\n            of the matrix\n            <jats:italic>A<\/jats:italic>\n            , denoted td\n            <jats:sub>\n              <jats:italic>D<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>A<\/jats:italic>\n            ), which is the treedepth of the graph over the rows of\n            <jats:italic>A<\/jats:italic>\n            , where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Kouteck\u00fd et al. that ILP F\n            <jats:sc>easibility<\/jats:sc>\n            can be solved in time \u2016A\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            <jats:sup>2<\/jats:sup>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (td\n              <jats:sub>\n                <jats:italic>D<\/jats:italic>\n              <\/jats:sub>\n              (\n              <jats:italic>A<\/jats:italic>\n              ))\n            <\/jats:sup>\n            \u22c5 (\n            <jats:italic>k<\/jats:italic>\n            + \u2113 + log \u2016b\u2016\n            <jats:sub>\u221e<\/jats:sub>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            . We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of\n            <jats:italic>A<\/jats:italic>\n            and b are in {\u22121, 0, 1}, the existence of an algorithm with running time 2\n            <jats:sup>2<\/jats:sup>\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (td\n              <jats:sub>\n                <jats:italic>D<\/jats:italic>\n              <\/jats:sub>\n              (\n              <jats:italic>A<\/jats:italic>\n              ))\n            <\/jats:sup>\n            \u22c5 (\n            <jats:italic>k<\/jats:italic>\n            + \u2113)\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            would contradict the exponential time hypothesis.\n          <\/jats:p>","DOI":"10.1145\/3397484","type":"journal-article","created":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T10:13:38Z","timestamp":1591006418000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints"],"prefix":"10.1145","volume":"12","author":[{"given":"Du\u0161an","family":"Knop","sequence":"first","affiliation":[{"name":"Czech Technical University in Prague, Jugosl\u00e1vsk\u00fdch partyz\u00e1n\u016f"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Banacha, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[{"name":"University of Warsaw and University of Oxford, Wolfson Building, Parks Road, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115446.3115612"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313906"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 22nd Conference on Learning Theory (COLT\u201909)","author":"Bshouty Nader H.","year":"2009"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-007-2"},{"key":"e_1_2_1_6_1","unstructured":"Timothy Chan Jacob W. Cooper Martin Kouteck\u00fd Daniel Kr\u00e1l and Krist\u00fdna Pek\u00e1rkov\u00e1. 2019. Optimal matrix tree-depth and a row-invariant parameterized algorithm for integer programming. arXiv:1907.06688.  Timothy Chan Jacob W. Cooper Martin Kouteck\u00fd Daniel Kr\u00e1l and Krist\u00fdna Pek\u00e1rkov\u00e1. 2019. Optimal matrix tree-depth and a row-invariant parameterized algorithm for integer programming. arXiv:1907.06688."},{"key":"e_1_2_1_7_1","volume-title":"Nonlinear Combinatorial Optimization, D.-Z. Du","author":"Chen Lin"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.178"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Marek Cygan Fedor V. Fomin \u0141ukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Micha\u0142 Pilipczuk and Saket Saurabh. 2015. Parameterized Algorithms. Springer.  Marek Cygan Fedor V. Fomin \u0141ukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Micha\u0142 Pilipczuk and Saket Saurabh. 2015. Parameterized Algorithms. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI\u201917)","author":"Dvo\u0159\u00e1k Pavel","year":"2017"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/179"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Eisenbrand Friedrich","year":"2018"},{"key":"e_1_2_1_13_1","unstructured":"Friedrich Eisenbrand Christoph Hunkenschr\u00f6der Kim-Manuel Klein Martin Kouteck\u00fd Asaf Levin and Shmuel Onn. 2019. An algorithmic theory of integer programming. arxiv:1904.01361.  Friedrich Eisenbrand Christoph Hunkenschr\u00f6der Kim-Manuel Klein Martin Kouteck\u00fd Asaf Levin and Shmuel Onn. 2019. An algorithmic theory of integer programming. arxiv:1904.01361."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340322"},{"key":"e_1_2_1_15_1","unstructured":"Fedor V. Fomin Fahad Panolan M. S. Ramanujan and Saket Saurabh. 2018. On the optimality of pseudo-polynomial algorithms for integer programming. arXiv:1607.05342.  Fedor V. Fomin Fahad Panolan M. S. Ramanujan and Saket Saurabh. 2018. On the optimality of pseudo-polynomial algorithms for integer programming. arXiv:1607.05342."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.12.006"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI\u201917)","author":"Ganian Robert"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010033"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0490-y"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science (ITCS\u201919)","author":"Jansen Klaus","year":"2019"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science (ITCS\u201919)","author":"Jansen Klaus","year":"2019"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2875343.2875346"},{"key":"e_1_2_1_26_1","series-title":"Lecture Notes in Computer Science","volume-title":"Integer Programming and Combinatorial Optimization","author":"Klein Kim-Manuel"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-017-0550-0"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS\u201917)","author":"Knop Du\u0161an","year":"2017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Du\u0161an Knop Martin Kouteck\u00fd and Matthias Mnich. 2019. Combinatorial n-fold integer programming and applications. Mathematical Programming. Online. DOI:https:\/\/doi.org\/10.1007\/s10107-019-01402-2  Du\u0161an Knop Martin Kouteck\u00fd and Matthias Mnich. 2019. Combinatorial n -fold integer programming and applications. Mathematical Programming. Online. DOI:https:\/\/doi.org\/10.1007\/s10107-019-01402-2","DOI":"10.1007\/s10107-019-01402-2"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Kouteck\u00fd Martin","year":"2018"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1965-034-2"},{"key":"e_1_2_1_33_1","volume-title":"MOS-SIAM Series on Optimization","volume":"14","author":"De Loera Jes\u00fas A.","year":"2013"},{"key":"e_1_2_1_34_1","first-page":"96","article-title":"Construction of signature codes and the coin weighing problem","volume":"25","author":"Martirosyan S. S.","year":"1989","journal-title":"Problems of Information Transmission"},{"key":"e_1_2_1_35_1","volume-title":"Algorithms and Combinatorics","volume":"28","author":"Ne\u0161et\u0159il Jaroslav","year":"2012"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322287"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397484","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397484","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:33Z","timestamp":1750193253000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397484"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3397484"],"URL":"https:\/\/doi.org\/10.1145\/3397484","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}