{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T23:13:54Z","timestamp":1648854834938},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","funder":[{"name":"European Research Council","award":["757481, 805241"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384326","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"source":"Crossref","is-referenced-by-count":3,"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"}]},{"given":"Sophie","family":"Huiberts","sequence":"additional","affiliation":[{"name":"CWI, Netherlands"}]},{"given":"Bento","family":"Natura","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, UK"}]},{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[{"name":"London School of Economics and Political Science, UK"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993"},{"key":"e_1_3_2_1_2_1","article-title":"Log-barrier interior point methods are not strongly polynomial","volume":"2","author":"Allamigeon Xavier","year":"2018","journal-title":"SIAM Journal on Applied Algebra and Geometry"},{"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","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 938-942","author":"Cohen Michael B","year":"2019"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 40th annual ACM symposium on Theory of Computing. 451-460","author":"Daitch Samuel I","year":"2008"},{"key":"e_1_3_2_1_7_1","article-title":"On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds-Karp to Bland and Beyond","volume":"25","author":"De Loera Jes\u00fas A","year":"2015","journal-title":"SIAM Journal on Optimization"},{"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"},{"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"},{"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"},{"key":"e_1_3_2_1_13_1","volume-title":"Lara","author":"Gonzaga Clovis C.","year":"1997"},{"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","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"},{"key":"e_1_3_2_1_16_1","volume-title":"Atsumi Ohara Ohara, and Takashi Tsuchiya","author":"Kakihara Satoshi","year":"2014"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC). 302-311","author":"Karmarkar Narendra","year":"1984"},{"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","journal-title":"Doklady Academii Nauk SSSR"},{"key":"e_1_3_2_1_19_1","first-page":"1","article-title":"A bound for the number of diferent basic solutions generated by the simplex method","volume":"137","author":"Kitahara Tomonari","year":"2013","journal-title":"Mathematical Programming"},{"key":"e_1_3_2_1_20_1","article-title":"A simple variant of the MizunoTodd-Ye predictor-corrector algorithm and its objective-function-free complexity","volume":"23","author":"Kitahara Tomonari","year":"2013","journal-title":"SIAM Journal on Optimization"},{"key":"e_1_3_2_1_21_1","article-title":"A polynomial predictor-corrector trust-region algorithm for linear programming","volume":"19","author":"Lan Guanghui","year":"2009","journal-title":"SIAM Journal on Optimization"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 424-433","author":"Lee Yin Tat","year":"2014"},{"key":"e_1_3_2_1_23_1","volume-title":"2015 IEEE 56th Annual Symposium on Foundations of Computer Science. 230-249","author":"Lee Yin Tat","year":"2015"},{"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"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Science. IEEE, 253-262","author":"Madry Aleksander","year":"2013"},{"key":"e_1_3_2_1_26_1","article-title":"Towards a genuinely polynomial algorithm for linear programming","volume":"12","author":"Megiddo Nimrod","year":"1983","journal-title":"SIAM J. Comput."},{"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","article-title":"On the implementation of a primal-dual interior point method","volume":"2","author":"Mehrotra Sanjay","year":"1992","journal-title":"SIAM Journal on Optimization"},{"key":"e_1_3_2_1_29_1","unstructured":"Shinji Mizuno Michael Todd and Yinyu Ye. 1993. On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming. Mathematics of Operations Research-MOR 18 ( 11 1993 ) 964-981. https:\/\/doi.org\/10.1287\/moor.18.4. 964 10.1287\/moor.18.4.964 Shinji Mizuno Michael Todd and Yinyu Ye. 1993. On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming. Mathematics of Operations Research-MOR 18 ( 11 1993 ) 964-981. https:\/\/doi.org\/10.1287\/moor.18.4. 964 10.1287\/moor.18.4.964"},{"key":"e_1_3_2_1_30_1","volume-title":"Monteiro and Takashi Tsuchiya","author":"Renato","year":"2008"},{"key":"e_1_3_2_1_31_1","article-title":"A Variant of the Vavasis-Ye Layered-Step Interior-Point Algorithm for Linear Programming","volume":"13","author":"Monteiro Renato D. C.","year":"2003","journal-title":"SIAM Journal on Optimization"},{"key":"e_1_3_2_1_32_1","article-title":"A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm","volume":"15","author":"Monteiro Renato D. C.","year":"2005","journal-title":"SIAM Journal on Optimization"},{"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"},{"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","journal-title":"Mathematical Programming"},{"key":"e_1_3_2_1_35_1","article-title":"Is it possible to know a problem instance is ill-posed?: some foundations for a general theory of condition numbers","volume":"10","author":"Renegar James","year":"1994","journal-title":"Journal of Complexity"},{"key":"e_1_3_2_1_36_1","article-title":"Incorporating condition measures into the complexity theory of linear programming","volume":"5","author":"Renegar James","year":"1995","journal-title":"SIAM Journal on Optimization"},{"key":"e_1_3_2_1_37_1","volume-title":"Combinatorial Optimization-Polyhedra and Eficiency","author":"Schrijver Alexander"},{"key":"e_1_3_2_1_38_1","first-page":"1","article-title":"On the complexity of following the central path of linear programs by linear extrapolation II","volume":"52","author":"Sonnevend Gy\u00f6rgy","year":"1991","journal-title":"Mathematical Programming"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC).","author":"Spielman Daniel A","year":"2004"},{"key":"e_1_3_2_1_40_1","unstructured":"G.W. Stewart. 1989. On scaled projections and pseudoinverses. Linear Algebra Appl. 112 ( 1989 ) 189-193. https:\/\/doi.org\/10.1016\/ 0024-3795 ( 89 ) 90594-6 10.1016\/0024-3795(89)90594-6 G.W. Stewart. 1989. On scaled projections and pseudoinverses. Linear Algebra Appl. 112 ( 1989 ) 189-193. https:\/\/doi.org\/10.1016\/ 0024-3795 ( 89 ) 90594-6 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"},{"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","unstructured":"Michael J. Todd. 1990. A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm. Operations Research 38 6 ( 1990 ) 1006-1018. https:\/\/doi.org\/10.1287\/opre.38.6.1006 arXiv:https:\/\/doi.org\/10.1287\/opre.38.6. 1006 10.1287\/opre.38.6.1006 Michael J. Todd. 1990. A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm. Operations Research 38 6 ( 1990 ) 1006-1018. https:\/\/doi.org\/10.1287\/opre.38.6.1006 arXiv:https:\/\/doi.org\/10.1287\/opre.38.6. 1006 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"},{"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"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 30th IEEE Annual Symposium on Foundations of Computer Science. 332-337","author":"Vaidya Pravin M","year":"1989"},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA).","author":"van den Brand Jan","year":"2020"},{"key":"e_1_3_2_1_48_1","article-title":"Stable numerical algorithms for equilibrium systems","volume":"15","author":"Vavasis Stephen A","year":"1994","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"e_1_3_2_1_49_1","volume-title":"Vavasis and Yinyu Ye","author":"Stephen","year":"1996"},{"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."},{"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\/pdf\/10.1145\/3357713.3384326","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T22:09:14Z","timestamp":1624918154000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384326"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":53,"alternative-id":["10.1145\/3357713.3384326","10.1145\/3357713"],"URL":"http:\/\/dx.doi.org\/10.1145\/3357713.3384326","relation":{},"published":{"date-parts":[[2020,6,6]]}}}