{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:56:31Z","timestamp":1777362991461,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T00:00:00Z","timestamp":1738281600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T00:00:00Z","timestamp":1738281600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We obtain new transference bounds that connect the additive integrality gap and sparsity of solutions for integer linear programs. Specifically, we consider the integer programs\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\min \\{{\\varvec{c}}\\cdot {\\varvec{x}}: {\\varvec{x}}\\in P\\cap \\mathbb {Z}^n\\}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>min<\/mml:mo>\n                            <mml:mo>{<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>c<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u00b7<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>x<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>:<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>x<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u2208<\/mml:mo>\n                            <mml:mi>P<\/mml:mi>\n                            <mml:mo>\u2229<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>Z<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>}<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$P=\\{{\\varvec{x}}\\in \\mathbb {R}^n: \\varvec{A}{\\varvec{x}}={\\varvec{b}}, {\\varvec{x}}\\ge {\\varvec{0}}\\}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>P<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mo>{<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>x<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u2208<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>R<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>:<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>A<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mi>x<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>b<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mi>x<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo>\u2265<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mn>0<\/mml:mn>\n                            <\/mml:mrow>\n                            <mml:mo>}<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a polyhedron in the standard form determined by an integer\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$m\\times n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mo>\u00d7<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    matrix\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{A}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and an integer vector\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$${\\varvec{b}}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>b<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . The main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of the support of the optimal solutions corresponding to the vertices of the integer hull of\n                    <jats:italic>P<\/jats:italic>\n                    . Additionally, we obtain a new proximity estimate for the\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\ell _2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msub>\n                            <mml:mi>\u2113<\/mml:mi>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:msub>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -distance from a vertex of\n                    <jats:italic>P<\/jats:italic>\n                    to its nearest integer point in\n                    <jats:italic>P<\/jats:italic>\n                    . We also strengthen previously known bounds for the integer Carath\u00e9odory rank, a key sparsity characteristic which estimates the minimum size of the support of an integer point in\n                    <jats:italic>P<\/jats:italic>\n                    in terms of the matrix\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varvec{A}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . The proofs make use of the results from the geometry of numbers and convex geometry.\n                  <\/jats:p>","DOI":"10.1007\/s10107-024-02191-z","type":"journal-article","created":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T10:11:34Z","timestamp":1738318294000},"page":"29-48","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparsity and proximity transference in integer programming"],"prefix":"10.1007","volume":"216","author":[{"given":"Iskander","family":"Aliev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcel","family":"Celaya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Henk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,31]]},"reference":[{"key":"2191_CR1","unstructured":"Abdi, A., Cornu\u00e9jols, G., Guenin, B., Tun\u00e7el, L.: Dyadic linear programming and extensions. arXiv:2309.04601 (2023)"},{"key":"2191_CR2","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s10107-021-01657-8","volume":"192","author":"I Aliev","year":"2022","unstructured":"Aliev, I., Averkov, G., De Loera, J.A., Oertel, T.: Sparse representation of vectors in lattices and semigroups. Math. Program. 192, 519\u2013546 (2022)","journal-title":"Math. Program."},{"issue":"1","key":"2191_CR3","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1137\/20M1353228","volume":"31","author":"I Aliev","year":"2021","unstructured":"Aliev, I., Celaya, M., Henk, M., Williams, A.: Distance-sparsity transference for vertices of corner polyhedra. SIAM J. Optim. 31(1), 200\u2013216 (2021)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2191_CR4","doi-asserted-by":"publisher","first-page":"2152","DOI":"10.1137\/17M1162792","volume":"28","author":"I Aliev","year":"2018","unstructured":"Aliev, I., De Loera, J.A., Eisenbrand, F., Oertel, T., Weismantel, R.: The support of integer optimal solutions. SIAM J. Optim. 28(3), 2152\u20132157 (2018)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2191_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1137\/16M1083876","volume":"1","author":"I Aliev","year":"2017","unstructured":"Aliev, I., De Loera, J.A., Oertel, T., O\u2019Neill, C.: Sparse solutions of linear Diophantine equations. SIAM J. Appl. Algebra Geom. 1(1), 239\u2013253 (2017)","journal-title":"SIAM J. Appl. Algebra Geom."},{"issue":"1\u20132","key":"2191_CR6","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s10107-019-01392-1","volume":"182","author":"I Aliev","year":"2020","unstructured":"Aliev, I., Henk, M., Oertel, T.: Distances to lattice points in knapsack polyhedra. Math. Program. 182(1\u20132), 175\u2013198 (2020)","journal-title":"Math. Program."},{"key":"2191_CR7","doi-asserted-by":"crossref","unstructured":"Berndt, S., Jansen, K., Klein, K.-M.: New bounds for the vertices of the integer hull. In: Symposium on Simplicity in Algorithms (SOSA), pp. 25\u201336. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2021)","DOI":"10.1137\/1.9781611976496.3"},{"issue":"2","key":"2191_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0012-365X(77)90028-0","volume":"19","author":"CE Blair","year":"1977","unstructured":"Blair, C.E., Jeroslow, R.G.: The value function of a mixed integer program. I. Discrete Math. 19(2), 121\u2013138 (1977)","journal-title":"Discrete Math."},{"issue":"3","key":"2191_CR9","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF01583794","volume":"23","author":"CE Blair","year":"1982","unstructured":"Blair, C.E., Jeroslow, R.G.: The value function of an integer program. Math. Program. 23(3), 237\u2013273 (1982)","journal-title":"Math. Program."},{"key":"2191_CR10","doi-asserted-by":"crossref","unstructured":"Boche, H., Calderbank, R., Kutyniok, G., Vyb\u00edral, J.: A survey of compressed sensing. In: Compressed Sensing and its Applications. Appl. Numer. Harmon. Anal., pp. 1\u201339. Birkh\u00e4user\/Springer, Cham (2015)","DOI":"10.1007\/978-3-319-16042-9_1"},{"issue":"12","key":"2191_CR11","doi-asserted-by":"publisher","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"EJ Candes","year":"2005","unstructured":"Candes, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inform. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2191_CR12","volume-title":"An Introduction to the Geometry of Numbers. Classics in Mathematics","author":"JWS Cassels","year":"1996","unstructured":"Cassels, J.W.S.: An Introduction to the Geometry of Numbers. Classics in Mathematics. Springer Berlin Heidelberg, Berlin (1996)"},{"key":"2191_CR13","unstructured":"Celaya, M., Kuhlmann, S., Paat, J., Weismantel, R.: Improving the Cook et al. proximity bound given integral valued constraints. In: Integer Programming and Combinatorial Optimization. Lecture Notes in Comput. Sci, vol. 13265, pp. 84\u201397. Springer, Cham (2022)"},{"issue":"1","key":"2191_CR14","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0095-8956(86)90064-X","volume":"40","author":"W Cook","year":"1986","unstructured":"Cook, W., Fonlupt, J., Schrijver, A.: An integer analogue of Carath\u00e9odory\u2019s theorem. J. Comb. Theory Ser. B. 40(1), 63\u201370 (1986)","journal-title":"J. Comb. Theory Ser. B."},{"issue":"3","key":"2191_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01582230","volume":"34","author":"W Cook","year":"1986","unstructured":"Cook, W., Gerards, A.M.H., Schrijver, A., Tardos, \u00c9.: Sensitivity theorems in integer linear programming. Math. Program. 34(3), 251\u2013264 (1986)","journal-title":"Math. Program."},{"key":"2191_CR16","unstructured":"Dubey, Y., Liu, S.: A short proof of tight bounds on the smallest support size of integer solutions to linear equations. arXiv:2307.08826 (2023)"},{"issue":"5","key":"2191_CR17","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1016\/j.orl.2005.09.008","volume":"34","author":"F Eisenbrand","year":"2006","unstructured":"Eisenbrand, F., Shmonin, G.: Carath\u00e9odory bounds for integer cones. Oper. Res. Lett. 34(5), 564\u2013568 (2006)","journal-title":"Oper. Res. Lett."},{"key":"2191_CR18","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for integer programming using the Steinitz lemma. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 808\u2013816. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.52"},{"key":"2191_CR19","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1073\/pnas.53.2.260","volume":"53","author":"RE Gomory","year":"1965","unstructured":"Gomory, R.E.: On the relation between integer and noninteger solutions to linear programs. Proc. Natl. Acad. Sci. USA 53, 260\u2013265 (1965)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2191_CR20","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0024-3795(69)90017-2","volume":"2","author":"RE Gomory","year":"1969","unstructured":"Gomory, R.E.: Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2, 451\u2013558 (1969)","journal-title":"Linear Algebra Appl."},{"key":"2191_CR21","doi-asserted-by":"crossref","unstructured":"Lee, J., Paat, J., Stallknecht, I., Xu, L.: Improving proximity bounds using sparsity. In: Ba\u00efou, M., Gendron, B., G\u00fcnl\u00fck, O., Mahjoub, A. (eds.) Combinatorial Optimization. ISCO 2020. Lecture Notes in Computer Science, vol. 12176, pp. 115\u2013127. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-53262-8_10"},{"key":"2191_CR22","first-page":"2267","volume":"48","author":"J Lee","year":"2023","unstructured":"Lee, J., Paat, J., Stallknecht, I., Xu, L.: Polynomial upper bounds on the number of differing columns of $$\\Delta $$-modular integer programs. Math. Oper. Res. 48, 2267\u20132286 (2023)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"2191_CR23","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/19M1275954","volume":"4","author":"T Oertel","year":"2020","unstructured":"Oertel, T., Paat, J., Weismantel, R.: The distributions of functions related to parametric integer optimization. SIAM J. Appl. Algebra Geom. 4(3), 422\u2013440 (2020)","journal-title":"SIAM J. Appl. Algebra Geom."},{"issue":"1\u20132","key":"2191_CR24","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s10107-018-1323-z","volume":"179","author":"J Paat","year":"2020","unstructured":"Paat, J., Weismantel, R., Weltge, S.: Distances between optimal solutions of mixed-integer programs. Math. Program. 179(1\u20132), 455\u2013468 (2020)","journal-title":"Math. Program."},{"key":"2191_CR25","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)"},{"key":"2191_CR26","unstructured":"Seb\u0151, A.: Hilbert bases, Carath\u00e9odory\u2019s theorem and combinatorial optimization. In: Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, pp. 431\u2013455. University of Waterloo Press (1990)"},{"key":"2191_CR27","volume-title":"Diophantische Gleichungen. Ergebnisse der Mathematik","author":"T Skolem","year":"1938","unstructured":"Skolem, T.: Diophantische Gleichungen. Ergebnisse der Mathematik, vol. 5. Springer, Berlin (1938)"},{"issue":"2","key":"2191_CR28","doi-asserted-by":"publisher","first-page":"543","DOI":"10.2140\/pjm.1979.83.543","volume":"83","author":"JD Vaaler","year":"1979","unstructured":"Vaaler, J.D.: A geometric inequality with applications to linear forms. Pac. J. Math. 83(2), 543\u2013553 (1979)","journal-title":"Pac. J. Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02191-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02191-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02191-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:13:30Z","timestamp":1777360410000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02191-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,31]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["2191"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02191-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,31]]},"assertion":[{"value":"30 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}