{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T17:54:20Z","timestamp":1775325260715,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T00:00:00Z","timestamp":1770076800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T00:00:00Z","timestamp":1770076800000},"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":["Discrete Comput Geom"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00454-025-00814-6","type":"journal-article","created":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T14:27:54Z","timestamp":1770128874000},"page":"667-708","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes"],"prefix":"10.1007","volume":"75","author":[{"given":"Gilles","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Dadush","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uri","family":"Grupel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2633-014X","authenticated-orcid":false,"given":"Sophie","family":"Huiberts","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Galyna","family":"Livshyts","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,3]]},"reference":[{"issue":"4","key":"814_CR1","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1287\/moor.9.4.629","volume":"9","author":"ML Balinski","year":"1984","unstructured":"Balinski, M.L.: The Hirsch conjecture for dual transportation polyhedra. Math. Oper. Res. 9(4), 629\u2013633 (1984). https:\/\/doi.org\/10.1287\/moor.9.4.629","journal-title":"Math. Oper. Res."},{"issue":"2","key":"814_CR2","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/bf00334039","volume":"77","author":"I B\u00e1r\u00e1ny","year":"1988","unstructured":"B\u00e1r\u00e1ny, I., F\u00fcredi, Z.: On the shape of the convex hull of random points. Probab. Theory Relat. Fields 77(2), 231\u2013240 (1988). https:\/\/doi.org\/10.1007\/bf00334039","journal-title":"Probab. Theory Relat. Fields"},{"issue":"1","key":"814_CR3","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/s0021-9800(69)80007-4","volume":"7","author":"D Barnette","year":"1969","unstructured":"Barnette, D.: $${W}_v$$ paths on 3-polytopes. J. Combinatorial Theory 7(1), 62\u201370 (1969). https:\/\/doi.org\/10.1016\/s0021-9800(69)80007-4","journal-title":"J. Combinatorial Theory"},{"issue":"1","key":"814_CR4","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0012-365x(74)90016-8","volume":"10","author":"D Barnette","year":"1974","unstructured":"Barnette, D.: An upper bound for the diameter of a polytope. Discret. Math. 10(1), 9\u201313 (1974). https:\/\/doi.org\/10.1016\/0012-365x(74)90016-8","journal-title":"Discret. Math."},{"issue":"1","key":"814_CR5","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/s00454-014-9601-x","volume":"52","author":"N Bonifas","year":"2014","unstructured":"Bonifas, N., Di Summa, M., Eisenbrand, F., H\u00e4hnle, N., Niemeier, M.: On sub-determinants and the diameter of polyhedra. Discrete Comput. Geometry 52(1), 102\u2013115 (2014). https:\/\/doi.org\/10.1007\/s00454-014-9601-x","journal-title":"Discrete Comput. Geometry"},{"key":"814_CR6","doi-asserted-by":"publisher","unstructured":"Borgwardt, K.H.: The Simplex Method: a Probabilistic Analysis. Algorithms and Combinatorics: Study and Research Texts, vol. 1, p. 268. Springer, Berlin (1987). https:\/\/doi.org\/10.1007\/978-3-642-61578-8","DOI":"10.1007\/978-3-642-61578-8"},{"issue":"4","key":"814_CR7","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1287\/moor.24.4.925","volume":"24","author":"KH Borgwardt","year":"1999","unstructured":"Borgwardt, K.H.: Erratum: a sharp upper bound for the expected number of shadow vertices in LP-polyhedra under orthogonal projection on two-dimensional planes. Math. Oper. Res. 24(4), 925\u2013984 (1999). https:\/\/doi.org\/10.1287\/moor.24.4.925","journal-title":"Math. Oper. Res."},{"issue":"2","key":"814_CR8","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s186-1999-8373-5","volume":"49","author":"KH Borgwardt","year":"1999","unstructured":"Borgwardt, K.H., Huhn, P.: A lower bound on the average number of pivot-steps for solving linear programs valid for all variants of the simplex-algorithm. Math. Methods Oper. Res. 49(2), 175\u2013210 (1999). https:\/\/doi.org\/10.1007\/s186-1999-8373-5","journal-title":"Math. Methods Oper. Res."},{"issue":"1","key":"814_CR9","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10107-017-1176-x","volume":"171","author":"S Borgwardt","year":"2018","unstructured":"Borgwardt, S., De Loera, J.A., Finhold, E.: The diameters of network-flow polytopes satisfy the Hirsch conjecture. Math. Program. 171(1), 283\u2013309 (2018). https:\/\/doi.org\/10.1007\/s10107-017-1176-x","journal-title":"Math. Program."},{"issue":"1\u20132","key":"814_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1112\/S0025579300014364","volume":"48","author":"A Brieden","year":"2001","unstructured":"Brieden, A., Gritzmann, P., Kannan, R., Klee, V., Lov\u00e1sz, L., Simonovits, M.: Deterministic and randomized polynomial-time approximation of radii. Mathematika 48(1\u20132), 63\u2013105 (2001). https:\/\/doi.org\/10.1112\/S0025579300014364","journal-title":"Mathematika"},{"issue":"2","key":"814_CR11","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00493-006-0010-5","volume":"26","author":"G Brightwell","year":"2006","unstructured":"Brightwell, G., Van den Heuvel, J., Stougie, L.: A linear bound on the diameter of the transportation polytope. Combinatorica 26(2), 133\u2013139 (2006). https:\/\/doi.org\/10.1007\/s00493-006-0010-5","journal-title":"Combinatorica"},{"key":"814_CR12","unstructured":"Canonne, C.: A short note on Poisson tail-bounds. Github repository link: https:\/\/github.com\/ccanonne\/probabilitydistributiontoolbox\/blob\/master\/poissonconcentration.pdf (2019)"},{"issue":"4","key":"814_CR13","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1007\/s00454-016-9793-3","volume":"56","author":"D Dadush","year":"2016","unstructured":"Dadush, D., H\u00e4hnle, N.: On the shadow simplex method for curved polyhedra. Discrete Comput. Geom. 56(4), 882\u2013909 (2016). https:\/\/doi.org\/10.1007\/s00454-016-9793-3","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"814_CR14","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1137\/18M1197205","volume":"49","author":"D Dadush","year":"2020","unstructured":"Dadush, D., Huiberts, S.: A friendly smoothed analysis of the simplex method. SIAM J. Comput. 49(5), 449\u2013499 (2020). https:\/\/doi.org\/10.1137\/18M1197205","journal-title":"SIAM J. Comput."},{"issue":"3","key":"814_CR15","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/s00454-016-9762-x","volume":"55","author":"A Del Pia","year":"2016","unstructured":"Del Pia, A., Michini, C.: On the diameter of lattice polytopes. Discrete Comput. Geom. 55(3), 681\u2013687 (2016). https:\/\/doi.org\/10.1007\/s00454-016-9762-x","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"814_CR16","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/s10474-017-0777-4","volume":"154","author":"A Deza","year":"2018","unstructured":"Deza, A., Pournin, L.: Improved bounds on the diameter of lattice polytopes. Acta Math. Hungar. 154(2), 457\u2013469 (2018). https:\/\/doi.org\/10.1007\/s10474-017-0777-4","journal-title":"Acta Math. Hungar."},{"issue":"1","key":"814_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582563","volume":"64","author":"M Dyer","year":"1994","unstructured":"Dyer, M., Frieze, A.: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program. 64(1), 1\u201316 (1994). https:\/\/doi.org\/10.1007\/BF01582563","journal-title":"Math. Program."},{"issue":"4","key":"814_CR18","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1287\/moor.1100.0470","volume":"35","author":"F Eisenbrand","year":"2010","unstructured":"Eisenbrand, F., H\u00e4hnle, N., Razborov, A., Rothvoss, T.: Diameter of polyhedra: limits of abstraction. Math. Oper. Res. 35(4), 786\u2013794 (2010). https:\/\/doi.org\/10.1287\/moor.1100.0470","journal-title":"Math. Oper. Res."},{"issue":"1","key":"814_CR19","doi-asserted-by":"publisher","first-page":"14","DOI":"10.20382\/jocg.v7i1a5","volume":"7","author":"M Glisse","year":"2016","unstructured":"Glisse, M., Lazard, S., Michel, J., Pouget, M.: Silhouette of a random polytope. J. Comput. Geom. 7(1), 14 (2016). https:\/\/doi.org\/10.20382\/jocg.v7i1a5","journal-title":"J. Comput. Geom."},{"issue":"3","key":"814_CR20","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1137\/0121052","volume":"21","author":"RC Grinold","year":"1971","unstructured":"Grinold, R.C.: The Hirsch conjecture in Leontief substitution systems. SIAM J. Appl. Math. 21(3), 483\u2013485 (1971). https:\/\/doi.org\/10.1137\/0121052","journal-title":"SIAM J. Appl. Math."},{"key":"814_CR21","doi-asserted-by":"crossref","unstructured":"Huiberts, S., Lee, Y.T., Zhang, X.: Upper and lower bounds on the smoothed complexity of the simplex method. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 1904\u20131917 (2023)","DOI":"10.1145\/3564246.3585124"},{"issue":"3","key":"814_CR22","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1002\/rsa.20008","volume":"24","author":"S Janson","year":"2004","unstructured":"Janson, S.: Large deviations for sums of partly dependent random variables. Random Struct. Algorithms 24(3), 234\u2013248 (2004). https:\/\/doi.org\/10.1002\/rsa.20008","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"814_CR23","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/s0273-0979-1992-00285-9","volume":"26","author":"G Kalai","year":"1992","unstructured":"Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Am. Math. Soc. Bulletin. New Series 26(2), 315\u2013317 (1992). https:\/\/doi.org\/10.1090\/s0273-0979-1992-00285-9","journal-title":"Am. Math. Soc. Bulletin. New Series"},{"key":"814_CR24","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF02395040","volume":"117","author":"V Klee","year":"1967","unstructured":"Klee, V., Walkup, D.W., et al.: The $$d$$-step conjecture for polyhedra of dimension $$d<6$$. Acta Math. 117, 53\u201378 (1967). https:\/\/doi.org\/10.1007\/BF02395040","journal-title":"Acta Math."},{"issue":"1","key":"814_CR25","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0012-365X(92)90349-K","volume":"102","author":"P Kleinschmidt","year":"1992","unstructured":"Kleinschmidt, P., Onn, S.: On the diameter of convex polytopes. Discret. Math. 102(1), 75\u201377 (1992). https:\/\/doi.org\/10.1016\/0012-365X(92)90349-K","journal-title":"Discret. Math."},{"issue":"2","key":"814_CR26","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/s10107-016-1099-y","volume":"165","author":"J-P Labb\u00e9","year":"2017","unstructured":"Labb\u00e9, J.-P., Manneville, T., Santos, F.: Hirsch polytopes with exponentially long combinatorial segments. Math. Program. 165(2), 663\u2013688 (2017). https:\/\/doi.org\/10.1007\/s10107-016-1099-y","journal-title":"Math. Program."},{"issue":"1","key":"814_CR27","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1112\/plms\/s3-20.1.161","volume":"s3\u201320","author":"DG Larman","year":"1970","unstructured":"Larman, D.G.: Paths on polytopes. Proc. London Math. Soc. s3\u201320(1), 161\u2013178 (1970). https:\/\/doi.org\/10.1112\/plms\/s3-20.1.161","journal-title":"Proc. London Math. Soc."},{"key":"814_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics. Springer, New York (2002). https:\/\/doi.org\/10.1007\/978-1-4613-0039-7"},{"issue":"1","key":"814_CR29","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s10107-013-0723-3","volume":"147","author":"C Michini","year":"2014","unstructured":"Michini, C., Sassano, A.: The Hirsch conjecture for the fractional stable set polytope. Math. Program. 147(1), 309\u2013330 (2014). https:\/\/doi.org\/10.1007\/s10107-013-0723-3","journal-title":"Math. Program."},{"issue":"1\u20133","key":"814_CR30","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01589099","volume":"45","author":"D Naddef","year":"1989","unstructured":"Naddef, D.: The Hirsch conjecture is true for $$(0,1)$$-polytopes. Math. Program. Series A and B 45(1\u20133), 109\u2013110 (1989). https:\/\/doi.org\/10.1007\/BF01589099","journal-title":"Math. Program. Series A and B"},{"key":"814_CR31","doi-asserted-by":"publisher","unstructured":"Narayanan, H., Shah, R., Srivastava, N.: A Spectral Approach to Polytope Diameter. In: Braverman, M. (ed.) 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 215, pp. 108\u2013110822. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2022.108","DOI":"10.4230\/LIPIcs.ITCS.2022.108"},{"issue":"19","key":"814_CR32","doi-asserted-by":"publisher","first-page":"6065","DOI":"10.1093\/imrn\/rnv342","volume":"2016","author":"A Reznikov","year":"2016","unstructured":"Reznikov, A., Saff, E.: The covering radius of randomly distributed points on a manifold. Int. Math. Res. Not. 2016(19), 6065\u20136094 (2016). https:\/\/doi.org\/10.1093\/imrn\/rnv342","journal-title":"Int. Math. Res. Not."},{"key":"814_CR33","doi-asserted-by":"publisher","unstructured":"Sanit\u00e0, L.: The diameter of the fractional matching polytope and its hardness implications. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 910\u2013921 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00090. IEEE","DOI":"10.1109\/FOCS.2018.00090"},{"issue":"1","key":"814_CR34","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F Santos","year":"2012","unstructured":"Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383\u2013412 (2012). https:\/\/doi.org\/10.4007\/annals.2012.176.1.7","journal-title":"Ann. Math."},{"key":"814_CR35","doi-asserted-by":"publisher","unstructured":"Schneider, R., Weil, W.: Stochastic and Integral Geometry. Probability and its Applications (New York), p. 693. Springer Berlin, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78859-1","DOI":"10.1007\/978-3-540-78859-1"},{"issue":"3","key":"814_CR36","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004). https:\/\/doi.org\/10.1145\/990308.990310","journal-title":"J. ACM"},{"issue":"3","key":"814_CR37","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/s00454-018-0016-y","volume":"62","author":"N Sukegawa","year":"2019","unstructured":"Sukegawa, N.: An asymptotically improved upper bound on the diameter of polyhedra. Discrete Comput. Geom. 62(3), 690\u2013699 (2019). https:\/\/doi.org\/10.1007\/s00454-018-0016-y","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"814_CR38","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/140962310","volume":"28","author":"MJ Todd","year":"2014","unstructured":"Todd, M.J.: An improved Kalai-Kleitman bound for the diameter of a polyhedron. SIAM J. Discret. Math. 28(4), 1944\u20131947 (2014). https:\/\/doi.org\/10.1137\/140962310","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"814_CR39","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1137\/070683386","volume":"39","author":"R Vershynin","year":"2009","unstructured":"Vershynin, R.: Beyond hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method. SIAM J. Comput. 39(2), 646\u2013678 (2009). https:\/\/doi.org\/10.1137\/070683386. (Preliminary version in FOCS \u201806)","journal-title":"SIAM J. Comput."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00814-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-025-00814-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-025-00814-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T17:01:14Z","timestamp":1775322074000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-025-00814-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,3]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["814"],"URL":"https:\/\/doi.org\/10.1007\/s00454-025-00814-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,3]]},"assertion":[{"value":"31 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}