{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:00:37Z","timestamp":1762297237042,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,7,1]],"date-time":"2007-07-01T00:00:00Z","timestamp":1183248000000},"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":["J. ACM"],"published-print":{"date-parts":[[2007,7]]},"abstract":"<jats:p>A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single destination using a confluent flow. Single- and multi-commodity confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are (multi-commodity) confluent flows since Internet routing is destination based.<\/jats:p>\n          <jats:p>\n            We present near-tight approximation algorithms, hardness results, and existence theorems for minimizing congestion in single-commodity confluent flows. The maximum edge congestion of a single-commodity confluent flow occurs at one of the incoming edges of the destination. Therefore, finding a minimum-congestion confluent flow is equivalent to the following problem: given a directed graph\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>k<\/jats:italic>\n            <jats:italic>sinks<\/jats:italic>\n            and non-negative demands on all the nodes of\n            <jats:italic>G<\/jats:italic>\n            , determine a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized.\n          <\/jats:p>\n          <jats:p>\n            The main result of this article is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln(\n            <jats:italic>k<\/jats:italic>\n            ) in\n            <jats:italic>G<\/jats:italic>\n            , if\n            <jats:italic>G<\/jats:italic>\n            admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph\n            <jats:italic>G<\/jats:italic>\n            that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than\n            <jats:italic>H<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            , the\n            <jats:italic>k<\/jats:italic>\n            th harmonic number, thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>k<\/jats:italic>\n            )\/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if\n            <jats:italic>G<\/jats:italic>\n            admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in\n            <jats:italic>G<\/jats:italic>\n            with congestion at most 1 that satisfies 1\/3 fraction of total demand.\n          <\/jats:p>\n          <jats:p>\n            We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph is\n            <jats:italic>k<\/jats:italic>\n            -connected. In particular, we prove that\n            <jats:italic>k<\/jats:italic>\n            -connected graphs with\n            <jats:italic>k<\/jats:italic>\n            sinks admit confluent flows of congestion less than\n            <jats:italic>C<\/jats:italic>\n            +\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            , where\n            <jats:italic>C<\/jats:italic>\n            is the congestion of the best splittable flow, and\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>max<\/jats:sub>\n            is the maximum demand of any node in\n            <jats:italic>G<\/jats:italic>\n            . The proof of this existence theorem is non-constructive and relies on topological techniques introduced by Lov\u00e1sz.\n          <\/jats:p>","DOI":"10.1145\/1255443.1255444","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["(Almost) Tight bounds and existence theorems for single-commodity confluent flows"],"prefix":"10.1145","volume":"54","author":[{"given":"Jiangzhuo","family":"Chen","sequence":"first","affiliation":[{"name":"Virginia Tech, Blacksburg, Virginia"}]},{"given":"Robert D.","family":"Kleinberg","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, New York"}]},{"given":"L\u00e1szl\u00f3","family":"Lov\u00e1sz","sequence":"additional","affiliation":[{"name":"E\u00f6tv\u00f6s Lor\u00e1nd University, Budapest, Hungary"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, Massachusetts"}]},{"given":"Ravi","family":"Sundaram","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, Massachusetts"}]},{"given":"Adrian","family":"Vetta","sequence":"additional","affiliation":[{"name":"McGill University, Montreal, Quebec, Canada"}]}],"member":"320","published-online":{"date-parts":[[2007,7]]},"reference":[{"volume-title":"Nonlinear Programming","author":"Bertsekas D.","key":"e_1_2_1_1_1","unstructured":"Bertsekas , D. 1999. Nonlinear Programming . Athena Scientific , Belmont, MA . Bertsekas, D. 1999. Nonlinear Programming. Athena Scientific, Belmont, MA."},{"volume-title":"Meet and merge: Approximation algorithms for confluent flows. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. 373--382","author":"Chen J.","key":"e_1_2_1_2_1","unstructured":"Chen , J. , Rajaraman , R. , and Sundaram , R . 2003 . Meet and merge: Approximation algorithms for confluent flows. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. 373--382 . 10.1145\/780542.780598 Chen, J., Rajaraman, R., and Sundaram, R. 2003. Meet and merge: Approximation algorithms for confluent flows. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. 373--382. 10.1145\/780542.780598"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s004930050043","article-title":"On the single-source unsplittable flow problem","volume":"19","author":"Dinitz Y.","year":"1999","unstructured":"Dinitz , Y. , Garg , N. , and Goemans , M. 1999 . On the single-source unsplittable flow problem . Combinatorica 19 , 17 -- 41 . Dinitz, Y., Garg, N., and Goemans, M. 1999. On the single-source unsplittable flow problem. Combinatorica 19, 17--41.","journal-title":"Combinatorica"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford Jr., L.","year":"1956","unstructured":"Ford , Jr., L. , and Fulkerson , D. 1956 . Maximal flow through a network . Canad. J. Math. 8 , 399 -- 404 . Ford, Jr., L., and Fulkerson, D. 1956. Maximal flow through a network. Canad. J. Math. 8, 399--404.","journal-title":"Canad. J. Math."},{"key":"e_1_2_1_6_1","unstructured":"Ford Jr. L. and Fulkerson D. 1962. Flows in Networks. Princeton University Press Princeton NJ.  Ford Jr. L. and Fulkerson D. 1962. Flows in Networks. Princeton University Press Princeton NJ."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","article-title":"The directed subgraph homeomorphism problem","volume":"10","author":"Fortune S.","year":"1980","unstructured":"Fortune , S. , Hopcroft , J. , and Wyllie , J. 1980 . The directed subgraph homeomorphism problem . Theoret. Comput. Sci. 10 , 111 -- 121 . Fortune, S., Hopcroft, J., and Wyllie, J. 1980. The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10, 111--121.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM","author":"Gupta A.","key":"e_1_2_1_10_1","unstructured":"Gupta , A. , Kleinberg , J. , Kumar , A. , Rastogi , R. , and Yener , B . 2001. Provisioning a virtual private network: A network design problem for multicommodity flow . In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM , New York. 10.1145\/380752.380830 Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., and Yener, B. 2001. Provisioning a virtual private network: A network design problem for multicommodity flow. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, New York. 10.1145\/380752.380830"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 5th Hungarian Combinatorial Colloquium","author":"Gy\u0151ri E.","year":"1976","unstructured":"Gy\u0151ri , E. 1976 . On division of graphs to connected subgraphs . In Proceedings of the 5th Hungarian Combinatorial Colloquium . Budapest, Hungary. Gy\u0151ri, E. 1976. On division of graphs to connected subgraphs. In Proceedings of the 5th Hungarian Combinatorial Colloquium. Budapest, Hungary."},{"volume-title":"Cambridge University Press","author":"Hatcher A.","key":"e_1_2_1_13_1","unstructured":"Hatcher , A. 2002. Algebraic Topology . Cambridge University Press , Cambridge, UK . Hatcher, A. 2002. Algebraic Topology. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90044-2"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Kleinberg J. M.","year":"1996","unstructured":"Kleinberg , J. M. 1996 . Single-source unsplittable flow . In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 68--77. Kleinberg, J. M. 1996. Single-source unsplittable flow. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 68--77."},{"volume-title":"Proceedings of the ACM SIGCOMM Conference. ACM","author":"Kumar A.","key":"e_1_2_1_16_1","unstructured":"Kumar , A. , Rastogi , R. , Silberschatz , A. , and Yener , B . 2001. Algorithms for provisioning virtual private networks in the hose model . In Proceedings of the ACM SIGCOMM Conference. ACM , New York, 135--148. 10.1145\/383059.383070 Kumar, A., Rastogi, R., Silberschatz, A., and Yener, B. 2001. Algorithms for provisioning virtual private networks in the hose model. In Proceedings of the ACM SIGCOMM Conference. ACM, New York, 135--148. 10.1145\/383059.383070"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_18_1","volume-title":"Tech. Rep. 2001-17, DIMACS. Apr.","author":"Lorenz D.","year":"2001","unstructured":"Lorenz , D. , Orda , A. , Raz , D. , and Shavitt , Y . 2001 . How good can IP routing be? Tech. Rep. 2001-17, DIMACS. Apr. Lorenz, D., Orda, A., Raz, D., and Shavitt, Y. 2001. How good can IP routing be? Tech. Rep. 2001-17, DIMACS. Apr."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01896190","article-title":"A homology theory for spanning trees of a graph","volume":"30","author":"Lov\u00e1sz L.","year":"1977","unstructured":"Lov\u00e1sz , L. 1977 . A homology theory for spanning trees of a graph . Acta Mathematica Academiae Scientiarum Hungaricae 30 , 3 - 4 , 241--251. Lov\u00e1sz, L. 1977. A homology theory for spanning trees of a graph. Acta Mathematica Academiae Scientiarum Hungaricae 30, 3-4, 241--251.","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1090\/S0002-9904-1977-14298-5","article-title":"A good algorithm for lexicographically optimal flows in multi-terminal networks","volume":"83","author":"Megiddo N.","year":"1977","unstructured":"Megiddo , N. 1977 . A good algorithm for lexicographically optimal flows in multi-terminal networks . Bull. AMS 83 , 3 (May), 407--409. Megiddo, N. 1977. A good algorithm for lexicographically optimal flows in multi-terminal networks. Bull. AMS 83, 3 (May), 407--409.","journal-title":"Bull. AMS"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/774749.774760"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255443.1255444","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1255443.1255444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:28Z","timestamp":1750278148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1255443.1255444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,7]]}},"alternative-id":["10.1145\/1255443.1255444"],"URL":"https:\/\/doi.org\/10.1145\/1255443.1255444","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2007,7]]},"assertion":[{"value":"2007-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}