{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:57Z","timestamp":1740109317959,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,3,18]],"date-time":"2022-03-18T00:00:00Z","timestamp":1647561600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,18]],"date-time":"2022-03-18T00:00:00Z","timestamp":1647561600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2046\/1, project ID: 390685689"],"award-info":[{"award-number":["EXC-2046\/1, project ID: 390685689"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study proximity bounds within a natural model of random integer programs of the type <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\max \\;\\varvec{c}^{\\top }\\varvec{x}:\\varvec{A}\\varvec{x}=\\varvec{b},\\,\\varvec{x}\\in {\\mathbb {Z}}_{\\ge 0}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>max<\/mml:mo>\n                    <mml:mspace\/>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>c<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mi>\u22a4<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mi>x<\/mml:mi>\n                    <\/mml:mrow>\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:mspace\/>\n                    <mml:mrow>\n                      <mml:mi>x<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>Z<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mo>\u2265<\/mml:mo>\n                        <mml:mn>0<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{A}\\in {\\mathbb {Z}}^{m\\times n}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>A<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>Z<\/mml:mi>\n                      <\/mml:mrow>\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:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is of rank <jats:italic>m<\/jats:italic>, <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{b}\\in {\\mathbb {Z}}^{m}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>b<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>Z<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mi>m<\/mml:mi>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{c}\\in {\\mathbb {Z}}^{n}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>c<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mo>\u2208<\/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:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In particular, we seek bounds for proximity in terms of the parameter <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta (\\varvec{A})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mi>A<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is the square root of the determinant of the Gram matrix <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{A}\\varvec{A}^{\\top }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mi>A<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>A<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mi>\u22a4<\/mml:mi>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{A}$$<\/jats:tex-math><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><\/jats:alternatives><\/jats:inline-formula>. We prove that, up to constants depending on <jats:italic>n<\/jats:italic> and <jats:italic>m<\/jats:italic>, the proximity is \u201cgenerally\u201d bounded by <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta (\\varvec{A})^{1\/(n-m)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mrow>\n                          <mml:mi>A<\/mml:mi>\n                        <\/mml:mrow>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mi>m<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is significantly better than the best deterministic bounds which are, again up to dimension constants, linear in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta (\\varvec{A})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mi>A<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10107-022-01786-8","type":"journal-article","created":{"date-parts":[[2022,3,18]],"date-time":"2022-03-18T10:04:59Z","timestamp":1647597899000},"page":"1201-1219","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Proximity bounds for random integer programs"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3480-4835","authenticated-orcid":false,"given":"Marcel","family":"Celaya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Henk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,18]]},"reference":[{"issue":"6","key":"1786_CR1","doi-asserted-by":"publisher","first-page":"2978","DOI":"10.1137\/090778043","volume":"20","author":"I Aliev","year":"2010","unstructured":"Aliev, I., Henk, M.: Feasibility of integer knapsacks. SIAM J. Optim. 20(6), 2978\u20132993 (2010)","journal-title":"SIAM J. Optim."},{"issue":"(1\u20132, Ser. A)","key":"1786_CR2","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, Ser. A)), 175\u2013198 (2020)","journal-title":"Math. Program."},{"key":"1786_CR3","series-title":"Mathematical Surveys and Monographs","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/202","volume-title":"Asymptotic Geometric Analysis: Part I","author":"S Artstein-Avidan","year":"2015","unstructured":"Artstein-Avidan, S., Giannopoulos, A., Milman, V.D.: Asymptotic Geometric Analysis: Part I. Mathematical Surveys and Monographs, vol. 202. American Mathematical Society, Providence (2015)"},{"key":"1786_CR4","series-title":"Springer Undergraduate Mathematics Series","volume-title":"Matrix Groups: An Introduction to Lie Group Theory","author":"A Baker","year":"2003","unstructured":"Baker, A.: Matrix Groups: An Introduction to Lie Group Theory. Springer Undergraduate Mathematics Series, Springer, London (2003)"},{"key":"1786_CR5","doi-asserted-by":"crossref","unstructured":"Borst, S., Dadush, D., Huiberts, S., Tiwari, S.: On the integrality gap of binary integer programs with gaussian data. In: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 12707, pp. 427\u2013442. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-73879-2_30"},{"key":"1786_CR6","doi-asserted-by":"crossref","unstructured":"Celaya, M., Henk, M.: Proximity bounds for random integer programs. In: Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 12707, pp. 413\u2013426. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-73879-2_29"},{"issue":"3","key":"1786_CR7","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."},{"issue":"1","key":"1786_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3340322","volume":"16","author":"F Eisenbrand","year":"2019","unstructured":"Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms 16(1), 1\u201314 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"1786_CR9","series-title":"A Wiley Publication in Mathematical Statistics","volume-title":"An Introduction to Probability Theory and Its Applications","author":"V Feller","year":"1968","unstructured":"Feller, V., Feller, W.: An Introduction to Probability Theory and Its Applications. A Wiley Publication in Mathematical Statistics, vol. 1. Wiley, Hoboken (1968)"},{"key":"1786_CR10","series-title":"Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts","volume-title":"Real Analysis: Modern Techniques and Their Applications","author":"GB Folland","year":"1999","unstructured":"Folland, G.B.: Real Analysis: Modern Techniques and Their Applications. Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts, Wiley, Hoboken (1999)"},{"issue":"2","key":"1786_CR11","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. U.S.A. 53(2), 260 (1965)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"1786_CR12","series-title":"Fundamental Principles of Mathematical Sciences","volume-title":"Convex and Discrete Geometry","author":"PM Gruber","year":"2007","unstructured":"Gruber, P.M.: Convex and Discrete Geometry. Fundamental Principles of Mathematical Sciences, vol. 336. Springer, Berlin (2007)"},{"key":"1786_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4679-0","volume-title":"Geometric Integration Theory. Cornerstones","author":"SG Krantz","year":"2008","unstructured":"Krantz, S.G., Parks, H.R.: Geometric Integration Theory. Cornerstones. Birkh\u00e4user, Boston (2008)"},{"issue":"3","key":"1786_CR14","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","key":"1786_CR15","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF01489457","volume":"125","author":"WM Schmidt","year":"1998","unstructured":"Schmidt, W.M.: The distribution of sublattices of $${\\mathbf{Z}}^m$$. Monatshefte Math. 125(1), 37\u201381 (1998)","journal-title":"Monatshefte Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01786-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01786-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01786-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:19:38Z","timestamp":1675703978000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01786-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,18]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1786"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01786-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2022,3,18]]},"assertion":[{"value":"31 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}