{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:50:21Z","timestamp":1744217421045},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1995,9]]},"DOI":"10.1007\/bf01299746","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T04:14:22Z","timestamp":1111724062000},"page":"425-434","source":"Crossref","is-referenced-by-count":10,"title":["Improved bounds on the max-flow min-cut ratio for multicommodity flows"],"prefix":"10.1007","volume":"15","author":[{"given":"Serge","family":"Plotkin","sequence":"first","affiliation":[]},{"given":"\ufffdva","family":"Tardos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"B. Awerbuch andT. Leighton: Improved approximation algorithms for the multicommodity flow problem and local competitive routing in dynamic networks, InProc. 26th Annual ACM Symposium on Theory of Computing, 487?495, 1994.","DOI":"10.1145\/195058.195238"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"G. Even, J. Naor, B. Schieber, andM. Sudan: Approximating minimum feedback sets and multi-cuts in directed graphs. Unpublished manuscript, May 1994.","DOI":"10.1007\/3-540-59408-6_38"},{"key":"CR3","volume-title":"Flows in Networks","author":"L. R. Ford Jr.","year":"1962","unstructured":"L. R. Ford, Jr. andD. R. Fulkerson:Flows in Networks, Princeton Univ. Press, Princeton, NJ, 1962."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"N. Garg, V. V. Vazirani, andM. Yannakakis: Approximate max-flow min-(multi)cut theorems and their applications, InProc. 25th Annual ACM Symposium on Theory of Computing, May 1993.","DOI":"10.1145\/167088.167266"},{"key":"CR5","unstructured":"P. Klein, S. Plotkin, andS. Rao: Planar graphs, multicommodity flow, and network decomposition, InProc. 25th Annual ACM Symposium on Theory of Computing, May 1993."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"P. Klein, S. Plotkin, S. Rao, and\u00c9. Tardos: Bounds on the max-flow min-cut ratio for directed multicommodity flows, Technical Report CS-93-30, Brown University, September 1993.","DOI":"10.1145\/167088.167263"},{"issue":"2","key":"CR7","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF01200755","volume":"15 ({sn2","author":"P. N. Klein","year":"1995","unstructured":"P. N. Klein, S. Rao, A. Agrawal, andR. Ravi: An approximate max-flow min-cut relation for multicommodity flow, with applications,Combinatorica,15 (2) (1995), 187?202. Preliminary version appeared as ?Approximation through multicommodity flow,? InProc. 31th IEEE Annual Symposium on Foundations of Computer Science, 726?737, 1990.","journal-title":"Combinatorica"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"T. Leighton, F. Makedon, S. Plotkin, C. Stein, \u00c9. Tardos, andS. Tragoudas: Fast approximation algorithms for multicommodity flow problem, InProc. 23th ACM Symposium on the Theory of Computing, 101?111, May 1991.","DOI":"10.1145\/103418.103425"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"T. Leighton andS. Rao: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, InProc. 29th IEEE Annual Symposium on Foundations of Computer Science, 422?431, 1988.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","volume":"31","author":"H. Okamura","year":"1981","unstructured":"H. Okamura andP. D. Seymour: Multicommodity flows in planar graphs,J. Comb. Theory (B),31 75?81, 1981.","journal-title":"J. Comb. Theory (B)"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0195-6698(81)80033-9","volume":"2","author":"P. D. Seymour","year":"1981","unstructured":"P. D. Seymour: Matroids and multicommodity flows,European Journal of Combinatorics,2 257?290, 1981.","journal-title":"European Journal of Combinatorics"},{"issue":"2","key":"CR12","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P. D. Seymour","year":"1995","unstructured":"P. D. Seymour: Packing directed circuits fractionally,Combinatorica,15 (2) (1995), 281?288.","journal-title":"Combinatorica"},{"key":"CR13","unstructured":"S. Tragoudas: Improved approximations for the min-cut ratio and the flux,Mathematical Systems Theory, to appear."},{"key":"CR14","unstructured":"S. Tragoudas:VLSI partitioning approximation algorithms based on multicommodity flow and other techniques, PhD thesis, University of Texas at Dallas, 1991."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01299746.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01299746\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01299746","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:49:41Z","timestamp":1586180981000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01299746"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF01299746"],"URL":"https:\/\/doi.org\/10.1007\/bf01299746","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}