{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:49:46Z","timestamp":1775026186146,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,5,25]],"date-time":"2022-05-25T00:00:00Z","timestamp":1653436800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,5,25]],"date-time":"2022-05-25T00:00:00Z","timestamp":1653436800000},"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":["QIP\u2013805241"],"award-info":[{"award-number":["QIP\u2013805241"]}],"id":[{"id":"10.13039\/501100000781","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]]},"DOI":"10.1007\/s10107-022-01828-1","type":"journal-article","created":{"date-parts":[[2022,5,25]],"date-time":"2022-05-25T11:02:57Z","timestamp":1653476577000},"page":"1221-1263","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the integrality gap of binary integer programs with Gaussian data"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4001-6675","authenticated-orcid":false,"given":"Sander","family":"Borst","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5577-5012","authenticated-orcid":false,"given":"Daniel","family":"Dadush","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2633-014X","authenticated-orcid":false,"given":"Sophie","family":"Huiberts","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7987-1519","authenticated-orcid":false,"given":"Samarth","family":"Tiwari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,25]]},"reference":[{"key":"1828_CR1","volume-title":"The Probabilistic Method","author":"N Alon","year":"2005","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. John Wiley & Sons, Hoboken (2005)"},{"key":"1828_CR2","unstructured":"Beier, R., V\u00f6cking, B.: Probabilistic analysis of knapsack core algorithms. In: Munro, J.I. (ed.) Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11\u201314, 2004, pp. 468\u2013477. SIAM (2004)"},{"key":"1828_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-030-73879-2_30","volume-title":"Integer Programming and Combinatorial Optimization","author":"S Borst","year":"2021","unstructured":"Borst, S., Dadush, D., Huiberts, S., Tiwari, S.: On the integrality gap of binary integer programs with gaussian data. In: Singh, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, pp. 427\u2013442. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-73879-2_30"},{"key":"1828_CR4","doi-asserted-by":"publisher","unstructured":"Dadush, D., Huiberts, S.: A friendly smoothed analysis of the simplex method. SIAM J. Comput. 49(5), STOC18\u2013449 (2020). https:\/\/doi.org\/10.1137\/18M1197205","DOI":"10.1137\/18M1197205"},{"key":"1828_CR5","doi-asserted-by":"publisher","unstructured":"Dey, S.S., Dubey, Y., Molinaro, M.: Branch-and-bound solves random binary IPs in polytime. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 579\u2013591. Society for Industrial and Applied Mathematics (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.35","DOI":"10.1137\/1.9781611976465.35"},{"key":"1828_CR6","doi-asserted-by":"crossref","unstructured":"Dey, S.S., Dubey, Y., Molinaro, M.: Branch-and-bound solves random binary IPs in polytime. arXiv preprint arXiv:2007.15192 (v4) (2021)","DOI":"10.1007\/s10107-022-01895-4"},{"key":"1828_CR7","doi-asserted-by":"publisher","unstructured":"Doerr, B.: analyzing randomized search heuristics: tools from probability theory. In: Series on Theoretical Computer Science, pp. 1\u201320. World Scientific (2011). https:\/\/doi.org\/10.1142\/9789814282673_0001","DOI":"10.1142\/9789814282673_0001"},{"issue":"1\u20133","key":"1828_CR8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/bf01581197","volume":"55","author":"M Dyer","year":"1992","unstructured":"Dyer, M., Frieze, A.: Probabilistic analysis of the generalised assignment problem. Math. Program. 55(1\u20133), 169\u2013181 (1992). https:\/\/doi.org\/10.1007\/bf01581197","journal-title":"Math. Program."},{"issue":"1","key":"1828_CR9","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1287\/moor.14.1.162","volume":"14","author":"ME Dyer","year":"1989","unstructured":"Dyer, M.E., Frieze, A.M.: Probabilistic analysis of the multidimensional Knapsack problem. Math. OR 14(1), 162\u2013176 (1989). https:\/\/doi.org\/10.1287\/moor.14.1.162","journal-title":"Math. OR"},{"issue":"1","key":"1828_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3340322","volume":"16","author":"F Eisenbrand","year":"2020","unstructured":"Eisenbrand, F., Weismantel, R.: Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms 16(1), 1\u201314 (2020). https:\/\/doi.org\/10.1145\/3340322","journal-title":"ACM Trans. Algorithms"},{"key":"1828_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511794308","volume-title":"Compressed Sensing","year":"2009","unstructured":"Eldar, Y.C., Kutyniok, G. (eds.): Compressed Sensing. Cambridge University Press, Cambridge (2009). https:\/\/doi.org\/10.1017\/cbo9780511794308"},{"key":"1828_CR12","volume-title":"An Introduction to Probability Theory and its Applications","author":"W Feller","year":"1991","unstructured":"Feller, W.: An Introduction to Probability Theory and its Applications, vol. 2. John Wiley & Sons, Hoboken (1991)"},{"issue":"1","key":"1828_CR13","first-page":"163","volume":"40","author":"M Fradelizi","year":"1999","unstructured":"Fradelizi, M.: Hyperplane sections of convex bodies in isotropic position. Beitr\u00e4ge Algebra Geom 40(1), 163\u2013183 (1999)","journal-title":"Beitr\u00e4ge Algebra Geom"},{"issue":"3","key":"1828_CR14","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/0218037","volume":"18","author":"ML Furst","year":"1989","unstructured":"Furst, M.L., Kannan, R.: Succinct certificates for almost all subset sum problems. SIAM J. Comput. 18(3), 550\u2013558 (1989). https:\/\/doi.org\/10.1137\/0218037","journal-title":"SIAM J. Comput."},{"key":"1828_CR15","unstructured":"Galvin, D.: Three tutorial lectures on entropy and counting. arXiv:1406.7872 [math] (2014)"},{"key":"1828_CR16","doi-asserted-by":"publisher","unstructured":"Goldberg, A.V., Marchetti-Spaccamela, A.: On finding the exact solution of a zero-one knapsack problem. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing\u2014STOC\u201984. ACM Press (1984). https:\/\/doi.org\/10.1145\/800057.808701","DOI":"10.1145\/800057.808701"},{"key":"1828_CR17","doi-asserted-by":"publisher","unstructured":"Jansen, K., Rohwedder, L.: Integer Programming (2019). https:\/\/doi.org\/10.1002\/9781119454816.ch10","DOI":"10.1002\/9781119454816.ch10"},{"issue":"3","key":"1828_CR18","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. OR 12(3), 415\u2013440 (1987). https:\/\/doi.org\/10.1287\/moor.12.3.415","journal-title":"Math. OR"},{"issue":"4","key":"1828_CR19","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. OR 8(4), 538\u2013548 (1983). https:\/\/doi.org\/10.1287\/moor.8.4.538","journal-title":"Math. OR"},{"issue":"3","key":"1828_CR20","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/rsa.20135","volume":"30","author":"L Lov\u00e1sz","year":"2007","unstructured":"Lov\u00e1sz, L., Vempala, S.: The geometry of logconcave functions and sampling algorithms. Random Struct. Algorithms 30(3), 307\u2013358 (2007). https:\/\/doi.org\/10.1002\/rsa.20135","journal-title":"Random Struct. Algorithms"},{"key":"1828_CR21","doi-asserted-by":"publisher","unstructured":"Lueker, G.S.: On the average difference between the solutions to linear and Integer Knapsack problems. In: Applied Probability-Computer Science: The Interface, vol. 1, pp. 489\u2013504. Birkh\u00e4user, Boston (1982). https:\/\/doi.org\/10.1007\/978-1-4612-5791-2_22","DOI":"10.1007\/978-1-4612-5791-2_22"},{"key":"1828_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J Matousek","year":"2002","unstructured":"Matousek, J.: Lectures on Discrete Geometry, vol. 212. Springer, New York (2002). https:\/\/doi.org\/10.1007\/978-1-4613-0039-7"},{"issue":"4","key":"1828_CR23","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(4), 765\u2013768 (1981). https:\/\/doi.org\/10.1145\/322276.322287","journal-title":"J. ACM"},{"key":"1828_CR24","doi-asserted-by":"publisher","unstructured":"Pataki, G., Tural, M., Wong, E.B.: Basis Reduction and the complexity of branch-and-bound. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1254\u20131261. Society for Industrial and Applied Mathematics (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.100","DOI":"10.1137\/1.9781611973075.100"},{"key":"1828_CR25","first-page":"301","volume":"32","author":"A Pr\u00e9kopa","year":"1971","unstructured":"Pr\u00e9kopa, A.: Logarithmic concave measures with application to stochastic programming. Acta Sci. Math. 32, 301\u2013316 (1971)","journal-title":"Acta Sci. Math."},{"issue":"1","key":"1828_CR26","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10107-006-0055-7","volume":"110","author":"H R\u00f6glin","year":"2007","unstructured":"R\u00f6glin, H., V\u00f6cking, B.: Smoothed analysis of integer programming. Math. Program. 110(1), 21\u201356 (2007). https:\/\/doi.org\/10.1007\/s10107-006-0055-7","journal-title":"Math. Program."},{"key":"1828_CR27","doi-asserted-by":"crossref","unstructured":"Vershynin, R.: High-dimensional probability: An Introduction with Applications in Data Science. No.\u00a047 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2018)","DOI":"10.1017\/9781108231596"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01828-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01828-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01828-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:20:06Z","timestamp":1675704006000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01828-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,25]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1828"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01828-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,25]]},"assertion":[{"value":"1 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}