{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T03:52:03Z","timestamp":1778903523251,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T00:00:00Z","timestamp":1755561600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T00:00:00Z","timestamp":1755561600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["ScaleOpt-757481"],"award-info":[{"award-number":["ScaleOpt-757481"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["ForEFront-615640"],"award-info":[{"award-number":["ForEFront-615640"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007931","name":"Shanghai University of Finance and Economics","doi-asserted-by":"publisher","award":["2023110522"],"award-info":[{"award-number":["2023110522"]}],"id":[{"id":"10.13039\/501100007931","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012165","name":"Key Technologies Research and Development Program","doi-asserted-by":"publisher","award":["2023YFA1009500"],"award-info":[{"award-number":["2023YFA1009500"]}],"id":[{"id":"10.13039\/501100012165","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61932002"],"award-info":[{"award-number":["61932002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["101153187-NeurExCo"],"award-info":[{"award-number":["101153187-NeurExCo"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. From a theoretical perspective, linear convergence rates have been established for first order LP algorithms, despite the fact that the underlying formulations are not strongly convex. However, the convergence rate typically depends on the Hoffman constant of a large matrix that contains the constraint matrix, as well as the right hand side, cost, and capacity vectors. We introduce a first order approach for LP optimization with a convergence rate depending polynomially on the circuit imbalance measure, which is a geometric parameter of the constraint matrix, and depending logarithmically on the right hand side, capacity, and cost vectors. This provides much stronger convergence guarantees. For example, if the constraint matrix is totally unimodular, we obtain polynomial-time algorithms, whereas the convergence guarantees for approaches based on primal-dual formulations may have arbitrarily slow convergence rates for this class. Our approach is based on a fast gradient method due to Necoara, Nesterov, and Glineur (Math. Prog. 2019); this algorithm is called repeatedly in a framework that gradually fixes variables to the boundary. This technique is based on a new approximate version of Tardos\u2019s method, that was used to obtain a strongly polynomial algorithm for combinatorial LPs (Oper. Res. 1986).<\/jats:p>","DOI":"10.1007\/s10107-025-02264-7","type":"journal-article","created":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T13:03:45Z","timestamp":1755608625000},"page":"339-377","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A first order method for linear programming parameterized by circuit imbalance"],"prefix":"10.1007","volume":"216","author":[{"given":"Richard","family":"Cole","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5646-8567","authenticated-orcid":false,"given":"Christoph","family":"Hertrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yixin","family":"Tao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,19]]},"reference":[{"key":"2264_CR1","first-page":"20243","volume":"34","author":"D Applegate","year":"2021","unstructured":"Applegate, D., D\u00edaz, M., Hinder, O., et al.: Practical large-scale linear programming using primal-dual hybrid gradient. Adv. Neural. Inf. Process. Syst. 34, 20243\u201320257 (2021)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"issue":"1","key":"2264_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s10107-022-01901-9","volume":"201","author":"D Applegate","year":"2023","unstructured":"Applegate, D., Hinder, O., Lu, H., et al.: Faster first-order primal-dual methods for linear programming using restarts and sharpness. Math. Program. 201(1), 133\u2013184 (2023)","journal-title":"Math. Program."},{"key":"2264_CR3","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-031-59835-7_5","volume-title":"Integer Programming and Combinatorial Optimization","author":"R Cole","year":"2024","unstructured":"Cole, R., Hertrich, C., Tao, Y., et al.: A first order method for linear programming parameterized by circuit imbalance. In: Vygen, J., Byrka, J. (eds.) Integer Programming and Combinatorial Optimization, pp. 57\u201370. Springer Nature Switzerland, Cham (2024)"},{"key":"2264_CR4","doi-asserted-by":"crossref","unstructured":"Dadush, D., Natura, B., V\u00e9gh, L.A.: Revisiting Tardos\u2019s framework for linear programming: Faster exact solutions using approximate solvers. In: Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 931\u2013942 (2020)","DOI":"10.1109\/FOCS46700.2020.00091"},{"key":"2264_CR5","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10107-023-01956-2","volume":"204","author":"D Dadush","year":"2024","unstructured":"Dadush, D., Huiberts, S., Natura, B., et al.: A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. Math. Program. 204, 135\u2013206 (2024)","journal-title":"Math. Program."},{"key":"2264_CR6","unstructured":"Eckstein, J., Bertsekas, D.P., et\u00a0al.: An alternating direction method for linear programming. Tech. Rep. LIDS-P-1967 (1990)"},{"key":"2264_CR7","doi-asserted-by":"crossref","unstructured":"Ekbatani, F., Natura, B., V\u00e9gh, L.A.: Circuit imbalance measures and linear programming. In: Surveys in Combinatorics 2022, London Mathematical Society Lecture Note Series. Cambridge University Press, p 64\u2013114 (2022)","DOI":"10.1017\/9781009093927.004"},{"key":"2264_CR8","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s10107-024-02077-0","volume":"210","author":"S Fujishige","year":"2025","unstructured":"Fujishige, S., Kitahara, T., V\u00e9gh, L.A.: An update-and-stabilize framework for the minimum-norm-point problem. Math. Program. 210, 281\u2013311 (2025)","journal-title":"Math. Program."},{"key":"2264_CR9","first-page":"303","volume":"2","author":"D Fulkerson","year":"1968","unstructured":"Fulkerson, D.: Networks, frames, blocking systems. Mathematics of the Decision Sciences, Part I, Lectures in Applied Mathematics 2, 303\u2013334 (1968)","journal-title":"Mathematics of the Decision Sciences, Part I, Lectures in Applied Mathematics"},{"issue":"1\u20132","key":"2264_CR10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10107-010-0430-2","volume":"133","author":"A Gilpin","year":"2012","unstructured":"Gilpin, A., Pe\u00f1a, J., Sandholm, T.: First-order algorithm with convergence for-equilibrium in two-person zero-sum games. Math. Program. 133(1\u20132), 279\u2013298 (2012)","journal-title":"Math. Program."},{"key":"2264_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2024.107199","volume":"57","author":"O Hinder","year":"2024","unstructured":"Hinder, O.: Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs. Oper. Res. Lett. 57, 107199 (2024)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"2264_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.6028\/jres.049.027","volume":"49","author":"AJ Hoffman","year":"1952","unstructured":"Hoffman, A.J.: On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49(4), 263\u2013265 (1952)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"2264_CR13","doi-asserted-by":"crossref","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pp 302\u2013311 (1984)","DOI":"10.1145\/800057.808695"},{"key":"2264_CR14","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming. In: Doklady Academii Nauk SSSR, pp 1093\u20131096 (1979)"},{"key":"2264_CR15","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10107-018-1232-1","volume":"175","author":"I Necoara","year":"2019","unstructured":"Necoara, I., Nesterov, Y., Glineur, F.: Linear convergence of first order methods for non-strongly convex optimization. Math. Program. 175, 69\u2013107 (2019)","journal-title":"Math. Program."},{"key":"2264_CR16","unstructured":"Rockafellar, R.T.: The elementary vectors of a subspace of $$R^N$$. In: Combinatorial Mathematics and Its Applications: Proceedings North Carolina Conference, Chapel Hill, 1967. The University of North Carolina Press, pp 104\u2013127 (1969)"},{"key":"2264_CR17","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF03025291","volume":"20","author":"S Smale","year":"1998","unstructured":"Smale, S.: Mathematical problems for the next century. The Mathematical Intelligencer 20, 7\u201315 (1998)","journal-title":"The Mathematical Intelligencer"},{"issue":"3","key":"2264_CR18","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"\u00c9 Tardos","year":"1985","unstructured":"Tardos, \u00c9.: A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3), 247\u2013255 (1985)","journal-title":"Combinatorica"},{"key":"2264_CR19","doi-asserted-by":"crossref","unstructured":"Tardos, \u00c9.: A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research pp 250\u2013256 (1986)","DOI":"10.1287\/opre.34.2.250"},{"issue":"1","key":"2264_CR20","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s101070050087","volume":"86","author":"L Tun\u00e7el","year":"1999","unstructured":"Tun\u00e7el, L.: Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard. Math. Program. 86(1), 219\u2013223 (1999)","journal-title":"Math. Program."},{"issue":"1","key":"2264_CR21","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF02592148","volume":"74","author":"SA Vavasis","year":"1996","unstructured":"Vavasis, S.A., Ye, Y.: A primal-dual interior point method whose running time depends only on the constraint matrix. Math. Program. 74(1), 79\u2013120 (1996)","journal-title":"Math. Program."},{"key":"2264_CR22","unstructured":"Wang, S., Shroff, N.: A new alternating direction method for linear programming. Advances in Neural Information Processing Systems 30 (2017)"},{"issue":"1","key":"2264_CR23","first-page":"236","volume":"19","author":"T Yang","year":"2018","unstructured":"Yang, T., Lin, Q.: RSG: Beating subgradient method without smoothness and strong convexity. The Journal of Machine Learning Research 19(1), 236\u2013268 (2018)","journal-title":"The Journal of Machine Learning Research"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02264-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02264-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02264-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:13:10Z","timestamp":1777360390000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02264-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,19]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["2264"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02264-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,19]]},"assertion":[{"value":"17 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}