{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:59Z","timestamp":1781031419938,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":88,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"ANR","award":["ANRR-24-CE48-2762."],"award-info":[{"award-number":["ANRR-24-CE48-2762."]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800742","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"222-233","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1744-7789","authenticated-orcid":false,"given":"Eleon","family":"Bach","sequence":"first","affiliation":[{"name":"TU Munich, Munich, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7445-5820","authenticated-orcid":false,"given":"Alexander E.","family":"Black","sequence":"additional","affiliation":[{"name":"Bowdoin College, Brunswick, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2633-014X","authenticated-orcid":false,"given":"Sophie","family":"Huiberts","sequence":"additional","affiliation":[{"name":"CNRS, LIMOS, Aubiere, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0779-6801","authenticated-orcid":false,"given":"Sean","family":"Kafer","sequence":"additional","affiliation":[{"name":"Illinois State University, Normal, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(87)90007-0"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4222"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/223\/03132"},{"key":"e_1_3_2_1_4_1","volume-title":"How to use Farkas","author":"Andersen Erling D.","unstructured":"Erling D. Andersen. 2013. How to use Farkas\u2019 lemma to say something important about infeasible linear problems. MOSEK. https:\/\/docs.mosek.com\/whitepapers\/infeas.pdf"},{"key":"e_1_3_2_1_5_1","first-page":"35","article-title":"On the complexity of MINOS package for linear programming","volume":"13","author":"Andrei Neculai","year":"2004","unstructured":"Neculai Andrei. 2004. On the complexity of MINOS package for linear programming. Studies in Informatics and Control, 13, 1 (2004), 35\u201346.","journal-title":"Studies in Informatics and Control"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121192"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/focs63196.2025.00096"},{"key":"e_1_3_2_1_8_1","unstructured":"Keith Ball. 1997. Flavors of Geometry (MSRI Book Series Vol. 31). https:\/\/library.slmath.org\/books\/Book31\/files\/ball.pdf"},{"key":"e_1_3_2_1_9_1","volume-title":"Laurent El Ghaoui, and Arkadi Nemirovski","author":"Ben-Tal Aharon","year":"2009","unstructured":"Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. 2009. Robust Optimization. Princeton University Press. isbn:9780691143682 https:\/\/www2.isye.gatech.edu\/~nemirovs\/FullBookDec11.pdf"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.50.1.3.17780"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch63"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.0345"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-93112-3_7"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2.2.103"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261304"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Gilles Bonnet Daniel Dadush Uri Grupel Sophie Huiberts and Galyna Livshyts. 2026. Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes. Discrete & Computational Geometry Feb. issn:1432-0444 arxiv:2112.13027. https:\/\/doi.org\/10.1007\/s00454-025-00814-6 10.1007\/s00454-025-00814-6","DOI":"10.1007\/s00454-025-00814-6"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917108"},{"key":"e_1_3_2_1_18_1","unstructured":"Karl Heinz Borgwardt. 1977. Untersuchungen zur Asymptotik der mittleren Schrittzahl von Simplexverfahren in der linearen Optimierung. Ph. D. Dissertation. Universit\u00e4t Kaiserslautern."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61578-8"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.4.925"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_24"},{"key":"e_1_3_2_1_22_1","volume-title":"Experiments in Linear Programming","author":"Cutler Leola","unstructured":"Leola Cutler and Philip Wolfe. 1963. Experiments in Linear Programming. The RAND Corporation. https:\/\/apps.dtic.mil\/sti\/tr\/pdf\/AD0297757.pdf"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9793-3"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/18m1197205"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435.019"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179"},{"key":"e_1_3_2_1_27_1","volume-title":"Maximization of a linear function of variables subject to linear inequalities. Cowles Commission Monograph 13: Activity analysis of production and allocation, 339\u2013347","author":"Dantzig George B","unstructured":"George B Dantzig. 1951. Maximization of a linear function of variables subject to linear inequalities. Cowles Commission Monograph 13: Activity analysis of production and allocation, 339\u2013347."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","unstructured":"George B. Dantzig. 1990. Origins of the simplex method. 141\u2013151 pages. isbn:0201508141 https:\/\/doi.org\/10.1145\/87252.88081 10.1145\/87252.88081","DOI":"10.1145\/87252.88081"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.44"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01848-x"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2023.27"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf01582563"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1089-0"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009093927.004"},{"key":"e_1_3_2_1_35_1","unstructured":"FICO. 2023. FICO Xpress Optimizer Reference Manual. https:\/\/www.fico.com\/fico-xpress-optimization\/docs\/dms2023-04\/solver\/optimizer\/HTML\/chapter4.html?scroll=subsection400"},{"key":"e_1_3_2_1_36_1","unstructured":"Stefan Fischer. 1998. Zweidimensionale Projektionen von linearen Programmen. TU Berlin."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581089"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20807-2_16"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993675"},{"key":"e_1_3_2_1_40_1","volume-title":"The computational algorithm for the parametric objective function. Naval research logistics quarterly, 2, 1-2","author":"Gass Saul","year":"1955","unstructured":"Saul Gass and Thomas Saaty. 1955. The computational algorithm for the parametric objective function. Naval research logistics quarterly, 2, 1-2 (1955), 39\u201345."},{"key":"e_1_3_2_1_41_1","first-page":"10","article-title":"Electronic mail distribution of linear programming test problems","volume":"13","author":"Gay David M","year":"1985","unstructured":"David M Gay. 1985. Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Newsletter, 13 (1985), 10\u201312. https:\/\/netlib.org\/lp\/data\/","journal-title":"Mathematical Programming Society COAL Newsletter"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf01589114"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-020-00194-3"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-141050-6.50018-0"},{"key":"e_1_3_2_1_45_1","volume-title":"Worst case complexity of the shadow vertex simplex algorithm. preprint","author":"Goldfarb Donald","unstructured":"Donald Goldfarb. 1983. Worst case complexity of the shadow vertex simplex algorithm. preprint, Columbia University."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(79)90004-0"},{"key":"e_1_3_2_1_47_1","unstructured":"Gurobi Optimization LLC. 2025. Gurobi Optimizer Reference Manual. https:\/\/docs.gurobi.com\/_\/downloads\/optimizer\/en\/13.0\/pdf\/"},{"key":"e_1_3_2_1_48_1","volume-title":"The simplex method is very good! On the expected number of pivot steps and related properties of random linear programs","author":"Haimovich M.","unstructured":"M. Haimovich. 1983. The simplex method is very good! On the expected number of pivot steps and related properties of random linear programs. Columbia University."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-005-4802-0"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746557"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf01580108"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.201"},{"key":"e_1_3_2_1_53_1","volume-title":"High performance simplex solver. Ph. D. Dissertation","author":"Huangfu Qi","year":"1842","unstructured":"Qi Huangfu. 2013. High performance simplex solver. Ph. D. Dissertation. University of Edingburgh. http:\/\/hdl.handle.net\/1842\/7952"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-017-0130-5"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585124"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90171-4"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129759"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132524"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0482-y"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2012.01.004"},{"key":"e_1_3_2_1_61_1","volume-title":"How good is the simplex algorithm. Inequalities : III : proceedings of the 3rd Symposium on inequalities, 159\u2013175","author":"Klee Victor","unstructured":"Victor Klee and George J Minty. 1972. How good is the simplex algorithm. Inequalities : III : proceedings of the 3rd Symposium on inequalities, 159\u2013175."},{"key":"e_1_3_2_1_62_1","unstructured":"Achim Koberstein. 2005. The Dual Simplex Method Techniques for a fast and stable implementation. Ph. D. Dissertation. Universitat Paderborn. https:\/\/digital.ub.uni-paderborn.de\/hsmig\/content\/titleinfo\/3885\/full.pdf"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SEA.2024.18"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-59835-7_19"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-018-1276-4"},{"key":"e_1_3_2_1_66_1","unstructured":"Andrew Makhorin. 2017. GLPK (GNU Linear Programming Kit) documentation."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0257-9"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142678"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580645"},{"key":"e_1_3_2_1_70_1","unstructured":"MOSEK ApS. 2025. MOSEK Modeling Cookbook 3.4.0. https:\/\/docs.mosek.com\/modeling-cookbook\/index.html"},{"issue":"0","key":"e_1_3_2_1_71_1","first-page":"28","article-title":"MOSEK Optimizer API for Python","volume":"11","author":"MOSEK","year":"2025","unstructured":"MOSEK ApS. 2025. MOSEK Optimizer API for Python: Release 11.0.28. https:\/\/docs.mosek.com\/11.0\/pythonapi.pdf","journal-title":"Release"},{"key":"e_1_3_2_1_72_1","volume-title":"Encyclopedia of Optimization","author":"Murty K.","unstructured":"K. Murty. 2008. Complexity of degeneracy. In Encyclopedia of Optimization. Springer, 419\u2013425."},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120782"},{"key":"e_1_3_2_1_74_1","volume-title":"Advanced linear-programming computing techniques","author":"Orchard-Hays William","unstructured":"William Orchard-Hays. 1968. Advanced linear-programming computing techniques. McGraw-Hill."},{"key":"e_1_3_2_1_75_1","volume-title":"Manual for the RAND-IBM Code for Linear Programming","author":"Orchard-Hays William","unstructured":"William Orchard-Hays, Leola Cutler, and Harold Judd. 1956. Manual for the RAND-IBM Code for Linear Programming. The RAND Corporation."},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40754-3"},{"key":"e_1_3_2_1_77_1","unstructured":"Laurent Perron and Vincent Furnon. 2025. OR-Tools. https:\/\/developers.google.com\/optimization\/"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","unstructured":"Tim Roughgarden (Ed.). 2020. Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press. isbn:9781108494311 https:\/\/doi.org\/10.1017\/9781108637435 10.1017\/9781108637435","DOI":"10.1017\/9781108637435"},{"key":"e_1_3_2_1_79_1","unstructured":"Emanuel Schnalzger. 2014. Lineare Optimierung mit dem Schatteneckenalgorithmus im Kontext probabilistischer Analysen. Ph. D. Dissertation. Universit\u00e4t Augsburg. English translation by K.H. Borgwardt."},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139003858"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.33.3.301"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.23"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2019.02.003"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580646"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/bfb0120718"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683386"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0149"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800742","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:58:38Z","timestamp":1781027918000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800742"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":88,"alternative-id":["10.1145\/3798129.3800742","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800742","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}