{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:37Z","timestamp":1781305057932,"version":"3.54.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_16","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:34:29Z","timestamp":1781303669000},"page":"233-248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Circuit Diameter and\u00a0Straight Line Complexity"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Dadush","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Kober","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhuan Khye","family":"Koh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"issue":"1","key":"16_CR1","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1137\/17M1142132","volume":"2","author":"X Allamigeon","year":"2018","unstructured":"Allamigeon, X., Benchimol, P., Gaubert, S., Joswig, M.: Log-barrier interior point methods are not strongly polynomial. SIAM J. Appl. Algebra Geom. 2(1), 140\u2013178 (2018)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Allamigeon, X., Dadush, D., Loho, G., Natura, B., V\u00e9gh, L.A.: Interior point methods are not worse than simplex. SIAM J. Comput. (0), FOCS22-178 (2025)","DOI":"10.1137\/23M1554588"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Allamigeon, X., Gaubert, S., Vandame, N.: No self-concordant barrier interior point method is strongly polynomial. In: Leonardi, S., Gupta, A. (eds.) STOC 2022: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, 20\u201324 June 2022, pp. 515\u2013528. ACM (2022)","DOI":"10.1145\/3519935.3519997"},{"key":"16_CR4","unstructured":"Black, A.E., N\u00f6bel, C., Steiner, R.: Short circuit walks in fixed dimension. CoRR abs\/2510.01916 (2025)"},{"key":"16_CR5","unstructured":"Bland, R.G.: On the generality of network flow theory (1976), presented at the ORSA\/TIMS Joint National Meeting, Miami, FL"},{"issue":"1","key":"16_CR6","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1137\/140976868","volume":"29","author":"S Borgwardt","year":"2015","unstructured":"Borgwardt, S., Finhold, E., Hemmecke, R.: On the circuit diameter of dual transportation polyhedra. SIAM J. Discret. Math. 29(1), 113\u2013121 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"16_CR7","unstructured":"Dadush, D., Kober, S., Koh, Z.K.: On circuit diameter and straight line complexity. CoRR abs\/2602.05699 (2026)"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Dadush, D., Koh, Z.K., Natura, B., Olver, N., V\u00e9gh, L.A.: A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1561\u20131572 (2024)","DOI":"10.1145\/3618260.3649764"},{"issue":"1","key":"16_CR9","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/s10107-024-02107-x","volume":"206","author":"D Dadush","year":"2024","unstructured":"Dadush, D., Koh, Z.K., Natura, B., V\u00e9gh, L.A.: On circuit diameter bounds via circuit imbalances. Math. Program. 206(1), 631\u2013662 (2024)","journal-title":"Math. Program."},{"issue":"5","key":"16_CR10","first-page":"1277","volume":"11","author":"EA Dinic","year":"1970","unstructured":"Dinic, E.A.: Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady 11(5), 1277\u20131280 (1970)","journal-title":"Soviet Math. Doklady"},{"issue":"2","key":"16_CR11","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"LR Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"issue":"1","key":"16_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/17M1152115","volume":"33","author":"S Kafer","year":"2019","unstructured":"Kafer, S., Pashkovich, K., Sanit\u00e0, L.: On the circuit diameter of some combinatorial polytopes. SIAM J. Discret. Math. 33(1), 1\u201325 (2019)","journal-title":"SIAM J. Discret. Math."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Kalai, G.: Upper bounds for the diameter and height of graphs of convex polyhedra. Discret. Comput. Geom. 8, 363\u2013372 (1992)","DOI":"10.1007\/BF02293053"},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/S0273-0979-1992-00285-9","volume":"26","author":"G Kalai","year":"1992","unstructured":"Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Am. Math. Soc. 26(2), 315\u2013316 (1992)","journal-title":"Bull. Am. Math. Soc."},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0024-3795(89)90450-3","volume":"114","author":"J Lee","year":"1989","unstructured":"Lee, J.: Subspaces with well-scaled frames. Linear Algebra Appl. 114, 21\u201356 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"16_CR17","doi-asserted-by":"publisher","first-page":"2494","DOI":"10.1137\/151002915","volume":"25","author":"JAD Loera","year":"2015","unstructured":"Loera, J.A.D., Hemmecke, R., Lee, J.: On augmentation algorithms for linear and integer-linear programming: from Edmonds-Karp to bland and beyond. SIAM J. Optim. 25(4), 2494\u20132511 (2015)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"16_CR18","doi-asserted-by":"publisher","first-page":"2156","DOI":"10.1137\/21M1419994","volume":"32","author":"JAD Loera","year":"2022","unstructured":"Loera, J.A.D., Kafer, S., Sanit\u00e0, L.: Pivot rules for circuit-augmentation algorithms in linear optimization. SIAM J. Optim. 32(3), 2156\u20132179 (2022)","journal-title":"SIAM J. Optim."},{"issue":"5","key":"16_CR19","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0167-6377(00)00059-6","volume":"27","author":"ST McCormick","year":"2000","unstructured":"McCormick, S.T., Shioura, A.: Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks. Oper. Res. Lett. 27(5), 199\u2013207 (2000)","journal-title":"Oper. Res. Lett."},{"key":"16_CR20","unstructured":"Natura, B.: Circuit diameter of polyhedra is strongly polynomial. CoRR abs\/2602.06958 (2026)"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"N\u00f6bel, C., Steiner, R.: Complexity of polytope diameters via perfect matchings. In: Azar, Y., Panigrahi, D. (eds.) Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, 12\u201315 January 2025, pp. 2234\u20132251. SIAM (2025)","DOI":"10.1137\/1.9781611978322.74"},{"issue":"3","key":"16_CR22","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/s00454-018-0016-y","volume":"62","author":"N Sukegawa","year":"2019","unstructured":"Sukegawa, N.: An asymptotically improved upper bound on the diameter of polyhedra. Discret. Comput. Geom. 62(3), 690\u2013699 (2019)","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"16_CR23","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/140962310","volume":"28","author":"MJ Todd","year":"2014","unstructured":"Todd, M.J.: An improved Kalai-Kleitman bound for the diameter of a polyhedron. SIAM J. Discret. Math. 28(4), 1944\u20131947 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"16_CR24","unstructured":"Wallacher, C.: A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms (1989), unpublished manuscript, Institute f\u00fcr Angewandte Mathematik, Technische Universit\u00e4t Braunschweig"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Wulf, L.: Computing the polytope diameter is even harder than NP-hard (already for perfect matchings). CoRR abs\/2502.16398 (2025)","DOI":"10.1109\/FOCS63196.2025.00029"}],"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-032-28691-8_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:34:31Z","timestamp":1781303671000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"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":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}