{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:51:43Z","timestamp":1787503903381,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["757481, 805241"],"award-info":[{"award-number":["757481, 805241"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384326","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"761-774","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix"],"prefix":"10.1145","author":[{"given":"Daniel","family":"Dadush","sequence":"first","affiliation":[{"name":"CWI, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sophie","family":"Huiberts","sequence":"additional","affiliation":[{"name":"CWI, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bento","family":"Natura","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"R. K. Ahuja , T. L. Magnanti , and J. B. Orlin . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice-Hall, Inc. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1142132"},{"key":"e_1_3_2_1_3_1","unstructured":"S\u00e9bastien Bubeck and Ronen Eldan. 2014. The entropic barrier: a simple and optimal universal self-concordant barrier. arXiv preprint arXiv:1412. 1587.  S\u00e9bastien Bubeck and Ronen Eldan. 2014. The entropic barrier: a simple and optimal universal self-concordant barrier. arXiv preprint arXiv:1412. 1587."},{"key":"e_1_3_2_1_4_1","unstructured":"Sergei Chubanov. 2014. A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions. ( 2014 ). http:\/\/www.optimization-online.org\/DB_HTML\/ 2014 \/12\/4710.html.  Sergei Chubanov. 2014. A polynomial algorithm for linear optimization which is strongly polynomial under certain conditions on optimal solutions. ( 2014 ). http:\/\/www.optimization-online.org\/DB_HTML\/ 2014 \/12\/4710.html."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316303"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/151002915"},{"key":"e_1_3_2_1_8_1","volume-title":"Pivot Rules for CircuitAugmentation Algorithms in Linear Optimization. arXiv preprint arXiv","author":"De Loera Jes\u00fas A","year":"1909","unstructured":"Jes\u00fas A De Loera , Sean Kafer , and Laura Sanit\u00e0 . 2019. Pivot Rules for CircuitAugmentation Algorithms in Linear Optimization. arXiv preprint arXiv : 1909 . 12863 ( 2019 ). Jes\u00fas A De Loera, Sean Kafer, and Laura Sanit\u00e0. 2019. Pivot Rules for CircuitAugmentation Algorithms in Linear Optimization. arXiv preprint arXiv: 1909. 12863 ( 2019 )."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"II Dikin. 1967. Iterative solution of problems of linear and quadratic programming. Doklady Akademii Nauk 174 4 ( 1967 ) 747-748.  II Dikin. 1967. Iterative solution of problems of linear and quadratic programming. Doklady Akademii Nauk 174 4 ( 1967 ) 747-748.","DOI":"10.25291\/VR\/1967-VR-747"},{"key":"e_1_3_2_1_10_1","volume-title":"Connections in Combinatorial Optimization. Number 38 in Oxford Lecture Series in Mathematics and its Applications","author":"Frank Andr\u00e1s","unstructured":"Andr\u00e1s Frank . 2011. Connections in Combinatorial Optimization. Number 38 in Oxford Lecture Series in Mathematics and its Applications . Oxford University Press . Andr\u00e1s Frank. 2011. Connections in Combinatorial Optimization. Number 38 in Oxford Lecture Series in Mathematics and its Applications. Oxford University Press."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Jean-Louis Gofin. 1980. The relaxation method for solving systems of linear inequalities. Mathematics of Operations Research 5 3 ( 1980 ) 388-414.  Jean-Louis Gofin. 1980. The relaxation method for solving systems of linear inequalities. Mathematics of Operations Research 5 3 ( 1980 ) 388-414.","DOI":"10.1287\/moor.5.3.388"},{"key":"e_1_3_2_1_12_1","series-title":"SIAM review 34, 2 ( 1992 ), 167-224","volume-title":"Path-following methods for linear programming","author":"Gonzaga Clovis C","unstructured":"Clovis C Gonzaga . 1992. Path-following methods for linear programming . SIAM review 34, 2 ( 1992 ), 167-224 . Clovis C Gonzaga. 1992. Path-following methods for linear programming. SIAM review 34, 2 ( 1992 ), 167-224."},{"key":"e_1_3_2_1_13_1","volume-title":"Lara","author":"Gonzaga Clovis C.","year":"1997","unstructured":"Clovis C. Gonzaga and Hugo J . Lara . 1997 . A note on properties of condition numbers. Linear Algebra Appl . 261, 1 ( 1997 ), 269-273. Clovis C. Gonzaga and Hugo J. Lara. 1997. A note on properties of condition numbers. Linear Algebra Appl. 261, 1 ( 1997 ), 269-273."},{"key":"e_1_3_2_1_14_1","first-page":"93","article-title":"Reconciliation of Various Complexity and Condition Measures for Linear Programming Problems and a Generalization of Tardos","author":"Ho Jackie CK","year":"2002","unstructured":"Jackie CK Ho and Levent Tun\u00e7el . 2002 . Reconciliation of Various Complexity and Condition Measures for Linear Programming Problems and a Generalization of Tardos ' Theorem. In Foundations of Computational Mathematics. World Scientific , 93 - 147 . Jackie CK Ho and Levent Tun\u00e7el. 2002. Reconciliation of Various Complexity and Condition Measures for Linear Programming Problems and a Generalization of Tardos' Theorem. In Foundations of Computational Mathematics. World Scientific, 93-147.","journal-title":"Theorem. In Foundations of Computational Mathematics. World Scientific"},{"key":"e_1_3_2_1_15_1","volume-title":"Atsumi Ohara Ohara, and Takashi Tsuchiya","author":"Kakihara Satoshi","year":"2013","unstructured":"Satoshi Kakihara , Atsumi Ohara Ohara, and Takashi Tsuchiya . 2013 . Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs. Journal of Optimization Theory and Applications 157 ( 2013 ), 749-780. Satoshi Kakihara, Atsumi Ohara Ohara, and Takashi Tsuchiya. 2013. Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs. Journal of Optimization Theory and Applications 157 ( 2013 ), 749-780."},{"key":"e_1_3_2_1_16_1","volume-title":"Atsumi Ohara Ohara, and Takashi Tsuchiya","author":"Kakihara Satoshi","year":"2014","unstructured":"Satoshi Kakihara , Atsumi Ohara Ohara, and Takashi Tsuchiya . 2014 . Curvature integrals and iteration complexities in SDP and symmetric cone programs. Computational Optimization and Applications 57 ( 2014 ), 623-665. Satoshi Kakihara, Atsumi Ohara Ohara, and Takashi Tsuchiya. 2014. Curvature integrals and iteration complexities in SDP and symmetric cone programs. Computational Optimization and Applications 57 ( 2014 ), 623-665."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_3_2_1_18_1","first-page":"1093","article-title":"A polynomial algorithm in linear programming","volume":"244","author":"Khachiyan Leonid G","year":"1979","unstructured":"Leonid G Khachiyan . 1979 . A polynomial algorithm in linear programming . In Doklady Academii Nauk SSSR , Vol. 244. 1093 - 1096 . Leonid G Khachiyan. 1979. A polynomial algorithm in linear programming. In Doklady Academii Nauk SSSR, Vol. 244. 1093-1096.","journal-title":"Doklady Academii Nauk SSSR"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0482-y"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/110835475"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/070693461"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.23"},{"key":"e_1_3_2_1_24_1","volume-title":"Solving Linear Programs with O\u02dc (\u221arank) Linear System Solves. arXiv preprint","author":"Lee Yin Tat","year":"1910","unstructured":"Yin Tat Lee and Aaron Sidford . 2019. Solving Linear Programs with O\u02dc (\u221arank) Linear System Solves. arXiv preprint 1910 . 08033. Yin Tat Lee and Aaron Sidford. 2019. Solving Linear Programs with O\u02dc (\u221arank) Linear System Solves. arXiv preprint 1910. 08033."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212022"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Nimrod Megiddo Shinji Mizuno and Takashi Tsuchiya. 1998. A modified layeredstep interior-point algorithm for linear programming. Mathematical Programming 82 3 ( 1998 ) 339-355.  Nimrod Megiddo Shinji Mizuno and Takashi Tsuchiya. 1998. A modified layeredstep interior-point algorithm for linear programming. Mathematical Programming 82 3 ( 1998 ) 339-355.","DOI":"10.1007\/BF01580074"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0802028"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.4.964"},{"key":"e_1_3_2_1_30_1","volume-title":"Monteiro and Takashi Tsuchiya","author":"Renato","year":"2008","unstructured":"Renato D.C. Monteiro and Takashi Tsuchiya . 2008 . A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms. Mathematical Programming 115, 1 ( 2008 ), 105-149. Renato D.C. Monteiro and Takashi Tsuchiya. 2008. A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms. Mathematical Programming 115, 1 ( 2008 ), 105-149."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401388926"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402416803"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the Forty-Ninth Annual ACM Symposium on Theory of Computing (STOC). 100-111","author":"Olver Neil","unstructured":"Neil Olver and L\u00e1szl\u00f3 A. V\u00e9gh . 2017. A simpler and faster strongly polynomial algorithm for generalized flow maximization . In Proceedings of the Forty-Ninth Annual ACM Symposium on Theory of Computing (STOC). 100-111 . Neil Olver and L\u00e1szl\u00f3 A. V\u00e9gh. 2017. A simpler and faster strongly polynomial algorithm for generalized flow maximization. In Proceedings of the Forty-Ninth Annual ACM Symposium on Theory of Computing (STOC). 100-111."},{"key":"e_1_3_2_1_34_1","first-page":"1","article-title":"A polynomial-time algorithm, based on Newton's method, for linear programming","volume":"40","author":"Renegar James","year":"1988","unstructured":"James Renegar . 1988 . A polynomial-time algorithm, based on Newton's method, for linear programming . Mathematical Programming 40 , 1 - 3 ( 1988 ), 59-93. James Renegar. 1988. A polynomial-time algorithm, based on Newton's method, for linear programming. Mathematical Programming 40, 1-3 ( 1988 ), 59-93.","journal-title":"Mathematical Programming"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1001"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0805026"},{"key":"e_1_3_2_1_37_1","volume-title":"Combinatorial Optimization-Polyhedra and Eficiency","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 2003. Combinatorial Optimization-Polyhedra and Eficiency . Springer . Alexander Schrijver. 2003. Combinatorial Optimization-Polyhedra and Eficiency. Springer."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582904"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(89)90594-6"},{"key":"e_1_3_2_1_41_1","volume-title":"A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 3 (","author":"Tardos \u00c9va","year":"1985","unstructured":"\u00c9va Tardos . 1985. A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 3 ( 01 Sep 1985 ), 247-255. \u00c9va Tardos. 1985. A strongly polynomial minimum cost circulation algorithm. Combinatorica 5, 3 ( 01 Sep 1985 ), 247-255."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"\u00c9va Tardos. 1986. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research ( 1986 ) 250-256.  \u00c9va Tardos. 1986. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research ( 1986 ) 250-256.","DOI":"10.1287\/opre.34.2.250"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.38.6.1006"},{"key":"e_1_3_2_1_44_1","volume-title":"bounds, and probabilistic analysis of two complexity measures for linear programming problems. Mathematical Programming 90, 1 (","author":"Todd Michael J.","year":"2001","unstructured":"Michael J. Todd , Levent Tun\u00e7el , and Yinyu Ye. 2001. Characterizations , bounds, and probabilistic analysis of two complexity measures for linear programming problems. Mathematical Programming 90, 1 ( 01 Mar 2001 ), 59-69. Michael J. Todd, Levent Tun\u00e7el, and Yinyu Ye. 2001. Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems. Mathematical Programming 90, 1 ( 01 Mar 2001 ), 59-69."},{"key":"e_1_3_2_1_45_1","volume-title":"Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard. Mathematical Programming 86, 1 (","author":"Tun\u00e7el Levent","year":"1999","unstructured":"Levent Tun\u00e7el . 1999. Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard. Mathematical Programming 86, 1 ( 01 Sep 1999 ), 219-223. Levent Tun\u00e7el. 1999. Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard. Mathematical Programming 86, 1 ( 01 Sep 1999 ), 219-223."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.16"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892230948"},{"key":"e_1_3_2_1_49_1","volume-title":"Vavasis and Yinyu Ye","author":"Stephen","year":"1996","unstructured":"Stephen A. Vavasis and Yinyu Ye . 1996 . A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programming 74, 1 ( 1996 ), 79-120. Stephen A. Vavasis and Yinyu Ye. 1996. A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programming 74, 1 ( 1996 ), 79-120."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 A. V\u00e9gh. 2017. A Strongly Polynomial Algorithm for Generalized Flow Maximization. Mathematics of Operations Research 42 2 ( 2017 ) 179-211.  L\u00e1szl\u00f3 A. V\u00e9gh. 2017. A Strongly Polynomial Algorithm for Generalized Flow Maximization. Mathematics of Operations Research 42 2 ( 2017 ) 179-211.","DOI":"10.1287\/moor.2016.0800"},{"key":"e_1_3_2_1_51_1","volume-title":"Interior-Point Algorithms: Theory and Analysis","author":"Yinyu Ye.","unstructured":"Yinyu Ye. 1997. Interior-Point Algorithms: Theory and Analysis . John Wiley and Sons , New York . Yinyu Ye. 1997. Interior-Point Algorithms: Theory and Analysis. John Wiley and Sons, New York."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Yinyu Ye. 2005. A new complexity result on solving the Markov decision problem. Mathematics of Operations Research 30 3 ( 2005 ) 733-749.  Yinyu Ye. 2005. A new complexity result on solving the Markov decision problem. Mathematics of Operations Research 30 3 ( 2005 ) 733-749.","DOI":"10.1287\/moor.1050.0149"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Yinyu Ye. 2011. The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Mathematics of Operations Research 36 4 ( 2011 ) 593-603.  Yinyu Ye. 2011. The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Mathematics of Operations Research 36 4 ( 2011 ) 593-603.","DOI":"10.1287\/moor.1110.0516"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384326","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384326","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:32:57Z","timestamp":1750185177000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384326"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":53,"alternative-id":["10.1145\/3357713.3384326","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384326","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}