{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:22:13Z","timestamp":1757452933535,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031598340"},{"type":"electronic","value":"9783031598357"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-59835-7_5","type":"book-chapter","created":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:05:03Z","timestamp":1716275103000},"page":"57-70","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A First Order Method for\u00a0Linear Programming Parameterized by\u00a0Circuit Imbalance"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5885-0222","authenticated-orcid":false,"given":"Richard","family":"Cole","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5646-8567","authenticated-orcid":false,"given":"Christoph","family":"Hertrich","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0573-1369","authenticated-orcid":false,"given":"Yixin","family":"Tao","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1152-200X","authenticated-orcid":false,"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,22]]},"reference":[{"key":"5_CR1","first-page":"20243","volume":"34","author":"D Applegate","year":"2021","unstructured":"Applegate, D., 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":"5_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., Lubin, M.: 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":"5_CR3","doi-asserted-by":"crossref","unstructured":"Dadush, D., Huiberts, S., Natura, B., V\u00e9gh, L.A.: A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. Math. Program. (2023). (in press)","DOI":"10.1007\/s10107-023-01956-2"},{"key":"5_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":"5_CR5","unstructured":"Eckstein, J., Bertsekas, D.P., et\u00a0al.: An alternating direction method for linear programming. Technical report LIDS-P-1967 (1990)"},{"key":"5_CR6","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, pp. 64\u2013114. Cambridge University Press (2022)","DOI":"10.1017\/9781009093927.004"},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-031-32726-1_11","volume-title":"Integer Programming and Combinatorial Optimization","author":"S Fujishige","year":"2023","unstructured":"Fujishige, S., Kitahara, T., V\u00e9gh, L.A.: An update-and-stabilize framework for the minimum-norm-point problem. In: Del Pia, A., Kaibel, V. (eds.) IPCO 2023. LNCS, vol. 13904, pp. 142\u2013156. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-32726-1_11"},{"issue":"1\u20132","key":"5_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10107-010-0430-2","volume":"133","author":"A Gilpin","year":"2012","unstructured":"Gilpin, A., Pena, 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":"5_CR9","doi-asserted-by":"crossref","unstructured":"Hinder, O.: Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs. arXiv preprint arXiv:2309.03988 (2023)","DOI":"10.1016\/j.orl.2024.107199"},{"issue":"4","key":"5_CR10","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":"5_CR11","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":"5_CR12","unstructured":"Khachiyan, L.G.: A polynomial algorithm in linear programming. In: Doklady Academii Nauk SSSR, vol.\u00a0244, pp. 1093\u20131096 (1979)"},{"key":"5_CR13","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":"5_CR14","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. Math. Intell. 20, 7\u201315 (1998)","journal-title":"Math. Intell."},{"issue":"3","key":"5_CR15","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":"5_CR16","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"\u00c9 Tardos","year":"1986","unstructured":"Tardos, \u00c9.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34, 250\u2013256 (1986)","journal-title":"Oper. Res."},{"issue":"1","key":"5_CR17","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":"5_CR18","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":"5_CR19","unstructured":"Wang, S., Shroff, N.: A new alternating direction method for linear programming. Adv. Neural Inf. Process. Syst. 30 (2017)"},{"issue":"1","key":"5_CR20","first-page":"236","volume":"19","author":"T Yang","year":"2018","unstructured":"Yang, T., Lin, Q.: RSG: beating subgradient method without smoothness and strong convexity. J. Mach. Learn. Res. 19(1), 236\u2013268 (2018)","journal-title":"J. Mach. Learn. Res."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-59835-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T14:31:17Z","timestamp":1732026677000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-59835-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031598340","9783031598357"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-59835-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ipco2024.ii.uni.wroc.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}