{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:04Z","timestamp":1750307944250,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,11,1]],"date-time":"2007-11-01T00:00:00Z","timestamp":1193875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,11]]},"abstract":"<jats:p>\n            The approximability of the maximum edge-disjoint paths problem (EDP) in directed graphs was seemingly settled by an \u03a9(\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>1\/2<\/jats:sup>\n            - \u03f5)-hardness result of Guruswami et al. [2003], and an\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>m<\/jats:italic>\n            ) approximation achievable via a natural multicommodity-flow-based LP relaxation as well as a greedy algorithm. Here\n            <jats:italic>m<\/jats:italic>\n            is the number of edges in the graph. We observe that the \u03a9(\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>1\/2<\/jats:sup>\n            - \u03f5)-hardness of approximation applies to\n            <jats:italic>sparse<\/jats:italic>\n            graphs, and hence when expressed as a function of\n            <jats:italic>n<\/jats:italic>\n            , that is, the number of vertices, only an \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/2<\/jats:sup>\n            - \u03f5)-hardness follows. On the other hand,\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>m<\/jats:italic>\n            )-approximation algorithms do not guarantee a\n            <jats:italic>sublinear<\/jats:italic>\n            (in terms of\n            <jats:italic>n<\/jats:italic>\n            ) approximation algorithm for\n            <jats:italic>dense<\/jats:italic>\n            graphs. We note that a similar gap exists in the known results on the integrality gap of the flow-based LP relaxation: an \u03a9(\u221a\n            <jats:italic>n<\/jats:italic>\n            ) lower bound and\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>m<\/jats:italic>\n            ) upper bound. Motivated by this discrepancy in the upper and lower bounds, we study algorithms for EDP in directed and undirected graphs and obtain improved approximation ratios. We show that the greedy algorithm has an approximation ratio of\n            <jats:italic>O<\/jats:italic>\n            (min(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            , \u221a\n            <jats:italic>m<\/jats:italic>\n            )) in undirected graphs and a ratio of\n            <jats:italic>O<\/jats:italic>\n            (min(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4\/5<\/jats:sup>\n            , \u221a\n            <jats:italic>m<\/jats:italic>\n            )) in directed graphs. For acyclic graphs we give an\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ln\n            <jats:italic>n<\/jats:italic>\n            ) approximation via LP rounding. These are the first sublinear approximation ratios for EDP. The results also extend to EDP with weights and to the uniform-capacity unsplittable flow problem (UCUFP).\n          <\/jats:p>","DOI":"10.1145\/1290672.1290683","type":"journal-article","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T14:24:58Z","timestamp":1196432698000},"page":"46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Edge-disjoint paths revisited"],"prefix":"10.1145","volume":"3","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana, IL"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}]}],"member":"320","published-online":{"date-parts":[[2007,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1172-z"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.2.255.12228"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0015-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"volume-title":"Paths, Flows and VLSI-Layout","author":"Frank A.","key":"e_1_2_1_7_1","unstructured":"Frank , A. 1990. Packing paths, cuts, and circuits---A survey . In Paths, Flows and VLSI-Layout , B. Korte et al., eds., Springer , 49--100. Frank, A. 1990. Packing paths, cuts, and circuits---A survey. In Paths, Flows and VLSI-Layout, B. Korte et al., eds., Springer, 49--100."},{"key":"e_1_2_1_8_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman New York."},{"volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 300--309","author":"Garg N.","key":"e_1_2_1_9_1","unstructured":"Garg , N. , and K\u00f6nemann , J . 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems . In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 300--309 . Garg, N., and K\u00f6nemann, J. 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 300--309."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0370-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00351-X"},{"key":"e_1_2_1_16_1","volume-title":"Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston","author":"Lawler E.","year":"1976","unstructured":"Lawler , E. 1976 . Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston , Austin, TX . Lawler, E. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, Austin, TX."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1661"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press New York.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press New York.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_21_1","unstructured":"Robertson N. and Seymour P. 1990. Outline of a disjoint paths algorithm. In Paths Flows and VLSI-Layout B. Korte et al. eds. Springer.  Robertson N. and Seymour P. 1990. Outline of a disjoint paths algorithm. In Paths Flows and VLSI-Layout B. Korte et al. eds. Springer."},{"volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","key":"e_1_2_1_22_1","unstructured":"Schrijver , A. 1986. Theory of Linear and Integer Programming . John Wiley , New York . Schrijver, A. 1986. Theory of Linear and Integer Programming. John Wiley, New York."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796366"},{"volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics","author":"Varadarajan K.","key":"e_1_2_1_24_1","unstructured":"Varadarajan , K. , and Venkataraman , G . 2004. Graph decomposition and a greedy algorithm for edge-disjoint paths . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics , Philadelphia, PA, 379--380. Varadarajan, K., and Venkataraman, G. 2004. Graph decomposition and a greedy algorithm for edge-disjoint paths. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, 379--380."},{"volume-title":"Introduction to Graph Theory","author":"West D. B.","key":"e_1_2_1_25_1","unstructured":"West , D. B. 1996. Introduction to Graph Theory . Prentice-Hall . West, D. B. 1996. Introduction to Graph Theory. Prentice-Hall."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290683","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1290672.1290683","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:25Z","timestamp":1750258345000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290683"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["10.1145\/1290672.1290683"],"URL":"https:\/\/doi.org\/10.1145\/1290672.1290683","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,11]]},"assertion":[{"value":"2007-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}