{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T08:19:46Z","timestamp":1775377186195,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585124","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1904-1917","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method"],"prefix":"10.1145","author":[{"given":"Sophie","family":"Huiberts","sequence":"first","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}]},{"given":"Xinzhi","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"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","doi-asserted-by":"publisher","DOI":"10.1287\/opre.35.4.489"},{"key":"e_1_3_2_1_5_1","volume-title":"Polyhedral Combinatorics","author":"Avis David","unstructured":"David Avis and Vasek Chv\u00e1tal . 1978. Notes on Bland\u2019s pivoting rule . In Polyhedral Combinatorics . Springer , Berlin, Heidelberg . 24\u201334. David Avis and Vasek Chv\u00e1tal. 1978. Notes on Bland\u2019s pivoting rule. In Polyhedral Combinatorics. Springer, Berlin, Heidelberg. 24\u201334."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.2.193.10561"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917108"},{"key":"e_1_3_2_1_8_1","volume-title":"The Simplex Method: A Probabilistic Analysis. 1","author":"Borgwardt Karl Heinz","unstructured":"Karl Heinz Borgwardt . 1987. The Simplex Method: A Probabilistic Analysis. 1 , Springer-Verlag , Berlin, Berlin , Heidelberg. Karl Heinz Borgwardt. 1987. The Simplex Method: A Probabilistic Analysis. 1, Springer-Verlag, Berlin, Berlin, Heidelberg."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.4.925"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/18m1197205"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108637435.019"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_25"},{"key":"e_1_3_2_1_13_1","volume-title":"Maximization of a linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13","author":"Dantzig George B","year":"1947","unstructured":"George B Dantzig . 1947. Maximization of a linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13 ( 1947 ), 339\u2013347. George B Dantzig. 1947. Maximization of a linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13 (1947), 339\u2013347."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.44"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v7i2a6"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01848-x"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20807-2_16"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993675"},{"key":"e_1_3_2_1_19_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. 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_20_1","unstructured":"Fran\u00e7ois Glineur. 2000. Computational Experiments With a Linear Approximation of Second-Order Cone Optimization. https:\/\/web.archive.org\/web\/20220505114903\/https:\/\/perso.uclouvain.be\/francois.glineur\/oldwww\/Papers\/Image0001.ps.gz \t\t\t\t  Fran\u00e7ois Glineur. 2000. Computational Experiments With a Linear Approximation of Second-Order Cone Optimization. https:\/\/web.archive.org\/web\/20220505114903\/https:\/\/perso.uclouvain.be\/francois.glineur\/oldwww\/Papers\/Image0001.ps.gz"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-141050-6.50018-0"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8330-5_2"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(79)90004-0"},{"key":"e_1_3_2_1_24_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 . 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_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746557"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90171-4"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129759"},{"key":"e_1_3_2_1_28_1","first-page":"159","article-title":"How good is the simplex algorithm","volume":"3","author":"Klee Victor","year":"1972","unstructured":"Victor Klee and George J Minty . 1972 . How good is the simplex algorithm . Inequalities , 3 , 3 (1972), 159 \u2013 175 . Victor Klee and George J Minty. 1972. How good is the simplex algorithm. Inequalities, 3, 3 (1972), 159\u2013175.","journal-title":"Inequalities"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142678"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580645"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581642"},{"key":"e_1_3_2_1_32_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. \t\t\t\t  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_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78859-1"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.33.3.301"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591902"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580646"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683386"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585124","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":38,"alternative-id":["10.1145\/3564246.3585124","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585124","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}