{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:48Z","timestamp":1787341428789,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["163071"],"award-info":[{"award-number":["163071"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"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\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1440140"],"award-info":[{"award-number":["DMS-1440140"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1522158"],"award-info":[{"award-number":["DMS-1522158"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740425"],"award-info":[{"award-number":["CCF-1740425"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The support of a vector is the number of nonzero components. We show that given an integral $m\\times n$ matrix $A$, the integer linear optimization problem $\\max\\{c^Tx : Ax = b, x \\ge 0, x \\in \\mathbb{Z}^n\\}$ has an optimal solution whose support is bounded by $2m \\, \\log (2 \\sqrt{m} \\| A \\|_\\infty)$, where $ \\| A \\|_\\infty$ is the largest absolute value of an entry of $A$. Compared to previous bounds, the one presented here is independent of the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.<\/jats:p>","DOI":"10.1137\/17m1162792","type":"journal-article","created":{"date-parts":[[2018,8,2]],"date-time":"2018-08-02T13:02:02Z","timestamp":1533214922000},"page":"2152-2157","source":"Crossref","is-referenced-by-count":23,"title":["The Support of Integer Optimal Solutions"],"prefix":"10.1137","volume":"28","author":[{"given":"I.","family":"Aliev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. A.","family":"De Loera","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F.","family":"Eisenbrand","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T.","family":"Oertel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Weismantel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1083876"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01393823"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90064-X"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01191202"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.09.008"},{"key":"atypb6","first-page":"808","author":"Eisenbrand F.","year":"2018","journal-title":"PA"},{"key":"atypb7","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , Ser. Books Math. Sci., W. H. Freeman and Co., San Francisco, CA, 1979."},{"key":"atypb8","first-page":"830","author":"Goemans M. X.","year":"2014","journal-title":"PA"},{"key":"atypb9","unstructured":"G. H. Hardy, E. M. Wright, D. R. Heath-Brown, and J. H. Silverman,\n                      An Introduction to the Theory of Numbers\n                      , Oxford University Press, Oxford, 2008."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/090749451"},{"key":"atypb11","unstructured":"K. Jansen, K.M. Klein, and J. Verschae,\n                      Closing the gap for makespan scheduling via sparsification techniques\n                      , in Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, LIPIcs 55, Dagstuhl Publishing, Wadern, 2016, Article no. 72; available athttp:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-013-2."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/120900095"},{"key":"atypb13","unstructured":"D. Knop, M. Koutecky\u0301, and M. Mnich,\n                      Combinatorial $n$-fold integer programming and applications\n                      , in Proceedings of the 25th European Symposium on Algorithms, LIPIcs 88, Dagstuhl Publishing, Wadern, 2017, Article no. 54; available athttp:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-049-1."},{"key":"atypb14","first-page":"215","author":"Kuncak V.","year":"2007","journal-title":"Berlin"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.07.004"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"N. J. A. Sloane,\n                      The On-Line Encyclopedia of Integer Sequences\n                      ,http:\/\/oeis.org, 2017.","DOI":"10.1090\/noti1734"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1162792","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:18:56Z","timestamp":1787339936000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1162792"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1162792"],"URL":"https:\/\/doi.org\/10.1137\/17m1162792","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}