{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T14:10:04Z","timestamp":1791123004383,"version":"4.1.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    It is shown that the minimum cut ratio is within a factor of O(log k) of the maximum concurrent flow for k-commodity flow instances with arbitrary capacities and demands. This improves upon the previously best-known bound of O(log\n                    <jats:sup>2<\/jats:sup>\n                    k ) and is existentially tight, up to a constant factor. An algorithm for finding a cut with ratio within a factor of O(log k) of the maximum concurrent flow, and thus of the optimal min-cut ratio, is presented.\n                  <\/jats:p>","DOI":"10.1137\/s0097539794285983","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"291-301","source":"Crossref","is-referenced-by-count":183,"title":["An\n                    <i>O<\/i>\n                    (log\n                    <i>k<\/i>\n                    ) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm"],"prefix":"10.1137","volume":"27","author":[{"given":"Yonatan","family":"Aumann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Rabani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"G. M. Adelson\u2010Welsky, E. A. Dinits, and A. V. Karzanov,\n                      Flow Algorithms\n                      , Nauka, Moscow, 1975 (in Russian)."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210602"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"R4","first-page":"231","volume":"2","author":"Bretagnolle Jean","year":"1965","journal-title":"Ann. Inst. H. Poincar\u00e9 Sect. B (N.S.)"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis,\n                      The complexity of multiway cuts\n                      , in Proc. of the 24th Annual ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 241\u2013251.","DOI":"10.1145\/129712.129736"},{"key":"R6","first-page":"0","volume":"55","author":"Deza Michel","year":"1994","journal-title":"J. Comput. Appl. Math."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056816"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"R9","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP\u2010Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"R10","unstructured":"N. Garg,\n                      A Deterministic O(logk)\u2010Approximation Algorithm for Sparsest\u2010Cut\n                      , 1995, preprint."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"N. Garg, V. V. Vazirani, and M. Yannakakis,\n                      Primal\u2010dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover\n                      , in Proc. 20th International Colloquium on Automata, Languages, and Programming, (ICALP \u201993), Springer\u2010Verlag, New York, 1993, pp. 64\u201375.","DOI":"10.1007\/3-540-56939-1_62"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"N. Garg, V. V. Vazirani, and M. Yannakakis,\n                      Approximate max\u2010flow min\u2010(multi)cut theorems and their applications\n                      , in Proc. of the 25th Annual ACM Symposium on Theory of Computing, ACM, New York, 1993, pp. 698\u2013707.","DOI":"10.1145\/167088.167266"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. X. Goemans and D. P. Williamson,\n                      .878\u2010approximation algorithms for MAX CUT and MAX 2SAT\n                      , in Proc. of the 26th Annual ACM Symposium on Theory of Computing, ACM, New York, 1994, pp. 422\u2013431.","DOI":"10.1145\/195058.195216"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1287\/opre.11.3.344"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"D. Karger, R. Motwani, and M. Sudan,\n                      Approximate graph coloring by semidefinite programming\n                      , in Proc. of the 35th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 2\u201313.","DOI":"10.1109\/SFCS.1994.365710"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Philip Klein, Ajit Agrawal, R. Ravi, Satish Rao, Approximation through multicommodity flow, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 726\u201373792j:90031","DOI":"10.1109\/FSCS.1990.89595"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Plotkin, and S. Rao,\n                      Excluded minors, network decomposition, and multicommodity flow\n                      , in Proc. of the 25th Annual ACM Symposium on Theory of Computing, ACM, New York, 1993, pp. 682\u2013690.","DOI":"10.1145\/167088.167261"},{"key":"R18","volume-title":"Paths, flows, and VLSI\u2010layout","author":"Korte Bernhard","year":"1990"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1020"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"F. T. Leighton and S. Rao,\n                      An approximate max\u2010flow min\u2010cut theorem for uniform multicommodity flow problems with applications to approximation algorithms\n                      , in Proc. of the 29th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1988, pp. 422\u2013431.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"N. Linial, E. London, and Y. Rabinovich,\n                      The geometry of graphs and some of its algorithmic applications\n                      , in Proc. of the 35th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 577\u2013591.","DOI":"10.1109\/SFCS.1994.365733"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90004-6"},{"key":"R24","first-page":"325","volume":"9","author":"Margulis G. A.","year":"1975","journal-title":"Problems Inform. Transmission","ISSN":"https:\/\/id.crossref.org\/issn\/0032-9460","issn-type":"print"},{"key":"R25","first-page":"51","volume":"33","author":"Matou\u0161ek Ji\u0159\u00ed","year":"1992","journal-title":"Comment. Math. Univ. Carolin."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"S. Plotkin and \u00c9. Tardos,\n                      Improved bounds on the max\u2010flow min\u2010cut ratio for multicommodity flows\n                      , in Proc. of the 25th Annual ACM Symposium on Theory of Computing, ACM, New York, 1993, pp. 691\u2013697.","DOI":"10.1145\/167088.167263"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.3.377"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100108"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(81)80033-9"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77620"},{"key":"R32","unstructured":"S. Tragoudas,\n                      VLSI Partitioning Approximation Algorithms Based on Multicommodity Flow and Other Techniques\n                      , Ph.D. thesis, University of Texas at Dallas, 1991."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-66037-5"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594937"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794285983","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:40Z","timestamp":1787336080000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794285983"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794285983"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794285983","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}