{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T08:33:38Z","timestamp":1793694818588,"version":"4.5.1"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>In this paper we introduce the circuit diameter of polyhedra, which is always bounded from above by the combinatorial diameter. We consider dual transportation polyhedra defined on general bipartite graphs. For complete $M{\\times}N$ bipartite graphs the Hirsch bound (M-1)(N-1) on the combinatorial diameter is a known tight bound [Math. Oper. Res., 9 (1984), pp. 629--633]. For the circuit diameter we show the much stronger bound M+N-2 for all dual transportation polyhedra defined on arbitrary bipartite graphs with $M{+}N$ nodes.<\/jats:p>","DOI":"10.1137\/140976868","type":"journal-article","created":{"date-parts":[[2015,1,15]],"date-time":"2015-01-15T11:46:28Z","timestamp":1421322388000},"page":"113-121","source":"Crossref","is-referenced-by-count":26,"title":["On the Circuit Diameter of Dual Transportation Polyhedra"],"prefix":"10.1137","volume":"29","author":[{"given":"Steffen","family":"Borgwardt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elisabeth","family":"Finhold","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raymond","family":"Hemmecke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,1,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.9.4.629"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"J. A. De Loera, R. Hemmecke, and M. Ko\u0308ppe,\n                      Algebraic and Geometric Ideas in the Theory of Discrete Optimization\n                      , MOS-SIAM Ser. Optim. 14, SIAM, Philadelphia, 2013.","DOI":"10.1137\/1.9781611972443"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"J. A. De Loera, R. Hemmecke, and J. Lee,\n                      Augmentation Algorithms for Linear and Integer Linear Programming\n                      , arXiv:1408.3518, 2014.","DOI":"10.1137\/151002915"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.06.006"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01681344"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0638-z"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0490-y"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0276-7"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02395040"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.11.007"},{"key":"atypb11","unstructured":"S. Onn,\n                      Nonlinear Discrete Optimization\n                      , Zur. Lect. Adv. Math., European Mathematical Society, 2010."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.176.1.7"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614622"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140976868","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:36:40Z","timestamp":1787319400000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140976868"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140976868"],"URL":"https:\/\/doi.org\/10.1137\/140976868","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}