{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T03:10:42Z","timestamp":1784257842727,"version":"3.55.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T00:00:00Z","timestamp":1644796800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T00:00:00Z","timestamp":1644796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norwegian Research Council","doi-asserted-by":"crossref","award":["MULTIVAL"],"award-info":[{"award-number":["MULTIVAL"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,3]]},"DOI":"10.1007\/s10107-022-01783-x","type":"journal-article","created":{"date-parts":[[2022,2,14]],"date-time":"2022-02-14T16:24:18Z","timestamp":1644855858000},"page":"561-593","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the optimality of pseudo-polynomial algorithms for integer programming"],"prefix":"10.1007","volume":"198","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":false,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,2,14]]},"reference":[{"key":"1783_CR1","doi-asserted-by":"crossref","unstructured":"Cunningham, W.\u00a0H., and Geelen, J.: On integer programming and the branch-width of the constraint matrix, in Proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization (IPCO), vol.\u00a04513 of Lecture Notes in Comput. Sci., Springer, 2007, pp.\u00a0158\u2013166","DOI":"10.1007\/978-3-540-72792-7_13"},{"key":"1783_CR2","doi-asserted-by":"crossref","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., and Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT, in Proceedings of the 27th IEEE Conference on Computational Complexity (CCC), IEEE, 2012, pp.\u00a074\u201384","DOI":"10.1109\/CCC.2012.36"},{"key":"1783_CR3","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.\u00a0V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S.: Parameterized Algorithms, Springer, 2015","DOI":"10.1007\/978-3-319-21275-3"},{"key":"1783_CR4","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.\u00a0M.\u00a0M., and Wojtaszczyk, J.\u00a0O.: Solving connectivity problems parameterized by treewidth in single exponential time, in Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2011, pp.\u00a0150\u2013159","DOI":"10.1109\/FOCS.2011.23"},{"key":"1783_CR5","doi-asserted-by":"crossref","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication, in Proceedings of the 14th Annual European Symposium on Algorithms (ESA), vol.\u00a04168 of Lecture Notes in Comput. Sci., Springer, Berlin, 2006, pp.\u00a0280\u2013291","DOI":"10.1007\/11841036_27"},{"key":"1783_CR6","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., and Weismantel, R.: Proximity results and faster algorithms for integer programming using the steinitz lemma, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2018, pp.\u00a0808\u2013816","DOI":"10.1137\/1.9781611975031.52"},{"key":"1783_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $$o(n^2)$$ problems in computational geometry. Comput. Geom. 5, 165\u2013185 (1995)","journal-title":"Comput. Geom."},{"key":"1783_CR8","doi-asserted-by":"crossref","unstructured":"Ganian, R., Ordyniak, S., and Ramanujan, M.\u00a0S.: Going beyond primal treewidth for (M)ILP, in Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, S.\u00a0P. Singh and S.\u00a0Markovitch, eds., AAAI Press, 2017, pp.\u00a0815\u2013821","DOI":"10.1609\/aaai.v31i1.10644"},{"key":"1783_CR9","doi-asserted-by":"publisher","first-page":"2042","DOI":"10.1109\/18.556701","volume":"42","author":"GB Horn","year":"1996","unstructured":"Horn, G.B., Kschischang, F.R.: On the intractability of permuting a block code to minimize trellis complexity. IEEE Trans. Inf. Theory 42, 2042\u20132048 (1996)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1783_CR10","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Computer Syst. Sci. 62, 367\u2013375 (2001)","journal-title":"J. Computer Syst. Sci."},{"key":"1783_CR11","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Computer Syst. Sci. 63, 512\u2013530 (2001)","journal-title":"J. Computer Syst. Sci."},{"key":"1783_CR12","unstructured":"Jansen, K., and Rohwedder, L.: On integer programming and convolution, in 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, vol.\u00a0124 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, pp.\u00a043:1\u201343:17"},{"key":"1783_CR13","doi-asserted-by":"crossref","unstructured":"Jeong, J., Kim, E.\u00a0J., and Oum, S.: Constructive algorithm for path-width of matroids, in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2016, pp.\u00a01695\u20131704","DOI":"10.1137\/1.9781611974331.ch116"},{"key":"1783_CR14","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R.: Minkowski\u2019s convex body theorem and integer programming. Math. Op. Res. 12, 415\u2013440 (1987)","journal-title":"Math. Op. Res."},{"key":"1783_CR15","unstructured":"Knop, D., Pilipczuk, M., and Wrochna, M.: Tight complexity lower bounds for integer linear programming with few constraints, in 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, vol.\u00a0126 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, pp.\u00a044:1\u201344:15"},{"key":"1783_CR16","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Op. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Op. Res."},{"key":"1783_CR17","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., and Saurabh, S.: Known algorithms on graphs on bounded treewidth are probably optimal, in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2011, pp.\u00a0777\u2013789","DOI":"10.1137\/1.9781611973082.61"},{"key":"1783_CR18","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1287\/ijoc.1120.0524","volume":"25","author":"S Margulies","year":"2013","unstructured":"Margulies, S., Ma, J., Hicks, I.V.: The Cunningham-Geelen method in practice: Branch-decompositions and integer programming. INFORMS J. Comput. 25, 599\u2013610 (2013)","journal-title":"INFORMS J. Comput."},{"key":"1783_CR19","first-page":"85","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth?, Theory of. Computing 6, 85\u2013112 (2010)","journal-title":"Computing"},{"key":"1783_CR20","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1145\/322276.322287","volume":"28","author":"CH Papadimitriou","year":"1981","unstructured":"Papadimitriou, C.H.: On the complexity of integer programming. J. ACM 28, 765\u2013768 (1981)","journal-title":"J. ACM"},{"key":"1783_CR21","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. obstructions to tree-decomposition. J. Combinatorial Theory Ser. B 52, 153\u2013190 (1991)","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"1783_CR22","doi-asserted-by":"crossref","unstructured":"van Rooij, J.\u00a0M.\u00a0M., Bodlaender, H.\u00a0L., and Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution, in Proceedings of the 17th Annual European Symposium on Algorithms (ESA), vol.\u00a05757 of Lecture Notes in Comput. Sci., Springer, 2009, pp.\u00a0566\u2013577","DOI":"10.1007\/978-3-642-04128-0_51"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01783-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01783-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01783-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T13:10:45Z","timestamp":1700226645000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01783-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,14]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1783"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01783-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,14]]},"assertion":[{"value":"2 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}