{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:38:56Z","timestamp":1750307936258,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"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,5]]},"abstract":"\n In the\n multicommodity rent-or-buy<\/jats:italic>\n (MROB) network design problems, we are given a network together with a set of\n k<\/jats:italic>\n terminal pairs (\n s<\/jats:italic>\n 1<\/jats:sub>\n ,\n t<\/jats:italic>\n 1<\/jats:sub>\n ), \u2026, (\n s<\/jats:italic>\n \n k<\/jats:italic>\n <\/jats:sub>\n ,\n t<\/jats:italic>\n \n k<\/jats:italic>\n <\/jats:sub>\n . The goal is to provision the network so that a given amount of flow can be shipped between\n s<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n and\n t<\/jats:italic>\n \n i<\/jats:italic>\n <\/jats:sub>\n for all 1 \u2264\n i<\/jats:italic>\n \u2264\n k<\/jats:italic>\n simultaneously. In order to provision the network, one can either\n rent<\/jats:italic>\n capacity on edges at some cost per unit of flow, or\n buy<\/jats:italic>\n them at some larger fixed cost. Bought edges have no incremental, flow-dependent cost. The overall objective is to minimize the total provisioning cost.\n <\/jats:p>\n Recently, Gupta et al. [2003a] presented a 12-approximation for the MROB problem. Their algroithm chooses a subset of the terminal pairs in the graph at random and then buys the edges of an approximate Steiner forest for these pairs. This technique had previously been introduced [Gupta et al. 2003b] for the single-sink rent-or-buy network design problem.<\/jats:p>\n In this article we give a 6.828-approximation for the MROB problem by refining the algorithm of Gupta et al. and simplifying their analysis. The improvement in our article is based on a more careful adaptation and simplified analysis of the primal-dual algorithm for the Steiner forest problem due to Agrawal et al. [1995]. Our result significantly reduces the gap between the single-sink and multisink case.<\/jats:p>","DOI":"10.1145\/1240233.1240246","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sharing the cost more efficiently"],"prefix":"10.1145","volume":"3","author":[{"given":"L.","family":"Becchetti","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Roma, Italy"}]},{"given":"J.","family":"K\u00f6nemann","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON"}]},{"given":"S.","family":"Leonardi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Roma, Italy"}]},{"given":"M.","family":"P\u00e1al","sequence":"additional","affiliation":[{"name":"Google Inc., New York, NY"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. 542--547","author":"Awerbuch B.","key":"e_1_2_1_2_1","unstructured":"Awerbuch , B. , and Azar , Y . 1997. Buy-at-Bulk network design . In Proceedings of the IEEE Symposium on Foundations of Computer Science. 542--547 . Awerbuch, B., and Azar, Y. 1997. Buy-at-Bulk network design. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 542--547."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1754"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132609"},{"key":"e_1_2_1_6_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Quide to the Theory of NP-Completeness. W. H. Freeman San Francisco. Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Quide to the Theory of NP-Completeness. W. H. Freeman San Francisco."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. 606--615","author":"Gupta A.","key":"e_1_2_1_8_1","unstructured":"Gupta , A. , Kumar , A. , Pal , M. , and Roughgarden , T . 2003a. Approximation via cost-sharing: A simple approximation algorithm for the multicommodity rent-or-buy problem . In Proceedings of the IEEE Symposium on Foundations of Computer Science. 606--615 . Gupta, A., Kumar, A., Pal, M., and Roughgarden, T. 2003a. Approximation via cost-sharing: A simple approximation algorithm for the multicommodity rent-or-buy problem. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 606--615."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780597"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007419"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380825"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. 333--344","author":"Kumar A.","key":"e_1_2_1_12_1","unstructured":"Kumar , A. , Gupta , A. , and Roughgarden , T . 2002. A constant-factor approximation algorithm for the multicommodity . In Proceedings of the IEEE Symposium on Foundations of Computer Science. 333--344 . Kumar, A., Gupta, A., and Roughgarden, T. 2002. A constant-factor approximation algorithm for the multicommodity. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 333--344."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science.","author":"P\u00e1l M.","year":"2003","unstructured":"P\u00e1l , M. , and Tardos , \u00c9. 2003 . Group strategyproof mechanisms via primal-dual algorithms . In Proceedings of the IEEE Symposium on Foundations of Computer Science. P\u00e1l, M., and Tardos, \u00c9. 2003. Group strategyproof mechanisms via primal-dual algorithms. In Proceedings of the IEEE Symposium on Foundations of Computer Science."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240246","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1240233.1240246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:08Z","timestamp":1750258328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240246"}},"subtitle":["Improved approximation for multicommodity rent-or-buy"],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1240233.1240246"],"URL":"https:\/\/doi.org\/10.1145\/1240233.1240246","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}