{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:49:44Z","timestamp":1775026184832,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,10,19]],"date-time":"2022-10-19T00:00:00Z","timestamp":1666137600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,19]],"date-time":"2022-10-19T00:00:00Z","timestamp":1666137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s10107-022-01895-4","type":"journal-article","created":{"date-parts":[[2022,10,19]],"date-time":"2022-10-19T11:02:54Z","timestamp":1666177374000},"page":"569-587","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Branch-and-bound solves random binary IPs in poly(n)-time"],"prefix":"10.1007","volume":"200","author":[{"given":"Santanu S.","family":"Dey","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3281-1102","authenticated-orcid":false,"given":"Yatharth","family":"Dubey","sequence":"additional","affiliation":[]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,19]]},"reference":[{"key":"1895_CR1","doi-asserted-by":"crossref","unstructured":"Santanu,\u00a0S.D., Yatharth, D., Marco, 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. SIAM (2021)","DOI":"10.1137\/1.9781611976465.35"},{"key":"1895_CR2","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"HL Alisa","year":"1960","unstructured":"Alisa, H.L., Alison, G.D.: An automatic method of solving discrete programming problems. Econometrica 28, 497\u2013520 (1960)","journal-title":"Econometrica"},{"key":"1895_CR3","volume-title":"Nemhauser and laurence\u00a0a wolsey, vol.\u00a055","author":"L George","year":"1999","unstructured":"George, L.: Integer and Combinatorial Optimization. In: Nemhauser and laurence\u00a0a wolsey, vol.\u00a055. Wiley, New Jersey (1999)"},{"key":"1895_CR4","volume-title":"Integer Programming","author":"C Michele","year":"2014","unstructured":"Michele, C., G\u00e9rard, C., Giacomo, Z., et al.: Integer Programming, vol. 271. Springer, New York (2014)"},{"issue":"4","key":"1895_CR5","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"WL Hendrik Jr","year":"1983","unstructured":"Hendrik, W.L., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"1895_CR6","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"WL Hendrik","year":"1982","unstructured":"Hendrik, W.L., Arjen, K.L., L\u00e1szl\u00f3, L., et al.: Factoring polynomials with rational coeficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"key":"1895_CR7","unstructured":"G\u00e1bor, P., Mustafa, T., Erick,\u00a0B.W. 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. SIAM (2010)"},{"issue":"3","key":"1895_CR8","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1287\/ijoc.12.3.192.12635","volume":"12","author":"A Karen","year":"2000","unstructured":"Karen, A., Robert, E.B., Cor, A.J.H., Arjen, K.L., Job, W.S.: Market split and basis reduction: towards a solution of the cornu\u00e9jols-dawande instances. INFORMS J. Comput. 12(3), 192\u2013202 (2000)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"1895_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10479-006-0091-y","volume":"149","author":"R Bixby","year":"2007","unstructured":"Bixby, R., Rothberg, E.: Progress in computational mixed integer programming-a look back from the other side of the tipping point. Ann. Oper. Res. 149(1), 37 (2007)","journal-title":"Ann. Oper. Res."},{"key":"1895_CR10","doi-asserted-by":"publisher","unstructured":"Thomas\u00a0F.C. (ed.).: Chapter 3: Large Sparse Linear Programming, pp. 35\u201346. Springer, Berlin Heidelberg, 1984. https:\/\/doi.org\/10.1007\/3-540-12914-6_3","DOI":"10.1007\/3-540-12914-6_3"},{"key":"1895_CR11","first-page":"9","volume-title":"Operations Research Proceedings 2012","author":"W Matthias","year":"2014","unstructured":"Matthias, W.: Sparsity of lift-and-project cutting planes. In: Operations Research Proceedings 2012, pp. 9\u201314. Springer, New York (2014)"},{"issue":"1\u20132","key":"1895_CR12","first-page":"329","volume":"154","author":"SD Santanu","year":"2015","unstructured":"Santanu, S.D., Marco, M., Qianyi, W.: Approximating polyhedra with sparse inequalities. Math. Program. 154(1\u20132), 329\u2013352 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"1895_CR13","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1287\/moor.2017.0866","volume":"43","author":"SD Santanu","year":"2018","unstructured":"Santanu, S.D., Marco, M., Qianyi, W.: Analysis of sparse cutting planes for sparse milps with applications to stochastic milps. Math. Oper. Res. 43(1), 304\u2013332 (2018)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"1895_CR14","doi-asserted-by":"publisher","first-page":"1402","DOI":"10.1287\/opre.28.6.1402","volume":"28","author":"Vasek Chv\u00e1tal","year":"1980","unstructured":"Chv\u00e1tal, Vasek: Hard knapsack problems. Oper. Res. 28(6), 1402\u20131411 (1980)","journal-title":"Oper. Res."},{"issue":"1","key":"1895_CR15","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF01580225","volume":"6","author":"GJ Robert","year":"1974","unstructured":"Robert, G.J.: Trivial integer programs unsolvable by branch-and-bound. Math. Program. 6(1), 105\u2013109 (1974)","journal-title":"Math. Program."},{"key":"1895_CR16","doi-asserted-by":"crossref","unstructured":"Sanjeeb, D.: An exponential lower bound on the length of some classes of branch-and-cut proofs. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 145\u2013160. Springer (2002)","DOI":"10.1007\/3-540-47867-1_11"},{"key":"1895_CR17","doi-asserted-by":"publisher","unstructured":"Kevin K.H., Cheung, A.M.G., Daniel\u00a0E.S.: Verifying integer programming results. In: Friedrich, E., Jochen, K. (eds.) Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, Volume 10328 of Lecture Notes in Computer Science, pp. 148\u2013160. Springer, 2017. https:\/\/doi.org\/10.1007\/978-3-319-59250-3_13","DOI":"10.1007\/978-3-319-59250-3_13"},{"issue":"3","key":"1895_CR18","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"AS Daniel","year":"2004","unstructured":"Daniel, A.S., Shang-Hua, T.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM (JACM) 51(3), 385\u2013463 (2004)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"1895_CR19","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1287\/ijoc.11.2.173","volume":"11","author":"TL Jeff","year":"1999","unstructured":"Jeff, T.L., Martin, W.P.S.: A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2), 173\u2013187 (1999)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"1895_CR20","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.orl.2004.04.002","volume":"33","author":"T Achterberg","year":"2005","unstructured":"Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42\u201354 (2005)","journal-title":"Oper. Res. Lett."},{"key":"1895_CR21","doi-asserted-by":"crossref","unstructured":"Lueker, G.S.: On the average difference between the solutions to linear and integer knapsack problems. In: Applied Probability \u2013 Computer Science, The Interface, vol.\u00a01. Birkh\u00e4user (1982)","DOI":"10.1007\/978-1-4899-4975-2_22"},{"key":"1895_CR22","unstructured":"Andrew,\u00a0V.G., Alberto, M.-S.: On finding the exact solution of a zero-one knapsack problem. In: Richard,\u00a0A.D. (ed.). STOC, pp. 359\u2013368. ACM (1984). URL http:\/\/dblp.uni-trier.de\/db\/conf\/stoc\/stoc84.html#GoldbergM84"},{"key":"1895_CR23","unstructured":"Ren\u00e9, B., Berthold, V.: Random knapsack in expected polynomial time. In: Lawrence\u00a0L.L., Michel,\u00a0X.G. (eds.) STOC, pp. 232\u2013241. ACM (2003). URL http:\/\/dblp.uni-trier.de\/db\/conf\/stoc\/stoc2003.html#BeierV03"},{"key":"1895_CR24","unstructured":"Ren\u00e9, B., Berthold V.: Probabilistic analysis of knapsack core algorithms. In: Ian Munro, J. (ed.) SODA, pp. 468\u2013477. SIAM (2004). URL http:\/\/dblp.uni-trier.de\/db\/conf\/soda\/soda2004.html#BeierV04"},{"issue":"1","key":"1895_CR25","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. Oper. Res. 14(1), 162\u2013176 (1989)","journal-title":"Math. Oper. Res."},{"key":"1895_CR26","doi-asserted-by":"crossref","unstructured":"Sander, B., Daniel, D., Sophie, H., Samarth, T.: On the integrality gap of binary integer programs with gaussian data. In: IPCO, pp. 427\u2013442 (2021)","DOI":"10.1007\/978-3-030-73879-2_30"},{"key":"1895_CR27","unstructured":"Alan,\u00a0M.F.: On the expected efficiency of branch and bound for the asymmetric tsp. (2020)"},{"key":"1895_CR28","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, New Year (2001)"},{"key":"1895_CR29","unstructured":"Aharon, B.-T., Arkadi, N.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM (2001)"},{"key":"1895_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596","volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics","author":"V Roman","year":"2018","unstructured":"Roman, V.: High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2018). https:\/\/doi.org\/10.1017\/9781108231596"},{"issue":"3","key":"1895_CR31","doi-asserted-by":"publisher","first-page":"465","DOI":"10.2307\/2046239","volume":"97","author":"B Keith","year":"1986","unstructured":"Keith, B.: Cube slicing in $$\\mathbb{R} ^n$$. Proc. Am. Math. Soc. 97(3), 465\u2013473 (1986)","journal-title":"Proc. Am. Math. Soc."},{"key":"1895_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22147-7","volume-title":"Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems","author":"V Koltchinskii","year":"2011","unstructured":"Koltchinskii, V.: Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems. Springer-Verlag, New York (2011)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01895-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01895-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01895-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T23:08:45Z","timestamp":1684451325000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01895-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,19]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1895"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01895-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,19]]},"assertion":[{"value":"1 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare that they have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}