{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:55Z","timestamp":1787340415500,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Gupta et al. [J. ACM, 54 (2007), article 11] and Gupta, Kumar, and Roughgarden [in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365\u2013372] recently developed an elegant framework for the development of randomized approximation algorithms for rent-or-buy network design problems. The essential building block of this framework is an approximation algorithm for the underlying network design problem that admits a strict cost sharing scheme. Such cost sharing schemes have also proven to be useful in the development of approximation algorithms in the context of two-stage stochastic optimization with recourse. The main contribution of this paper is to show that the Steiner forest problem admits cost shares that are 3-strict and 4-group-strict. As a consequence, we derive surprisingly simple approximation algorithms for the multicommodity rent-or-buy and the multicast rent-or-buy problems with approximation ratios 5 and 6, improving over the previous best approximation ratios of 6.828 and 12.8, respectively. We also show that no approximation ratio better than 4.67 can be achieved using the sample-and-augment framework in combination with the currently best known Steiner forest approximation algorithms. In the context of two-stage stochastic optimization, our result leads to a 6-approximation algorithm for the stochastic Steiner tree problem in the black-box model and a 5-approximation algorithm for the stochastic Steiner forest problem in the independent decision model.<\/jats:p>","DOI":"10.1137\/090767108","type":"journal-article","created":{"date-parts":[[2010,10,26]],"date-time":"2010-10-26T18:06:13Z","timestamp":1288116373000},"page":"3616-3632","source":"Crossref","is-referenced-by-count":4,"title":["Strict Cost Sharing Schemes for Steiner Forest"],"prefix":"10.1137","volume":"39","author":[{"given":"Lisa","family":"Fleischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guido","family":"Sch\u00e4fer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,10,26]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Andrews,\n                      Hardness of buy-at-bulk network design\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2004, pp. 115\u2013124.","DOI":"10.1109\/FOCS.2004.32"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and Y. Azar,\n                      Buy-at-bulk network design\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 1997, pp. 542\u2013547.","DOI":"10.1109\/SFCS.1997.646143"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      Probabilistic approximation of metric spaces and its algorithmic applications\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 1996, pp. 184\u2013193.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      On approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240246"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"J. Byrka, F. Grandoni, T. Rothvo\u00df, and L.  Sanit\u00e0,\n                      An improved LP-based approximation for Steiner tree\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2010, pp. 583\u2013592.","DOI":"10.1145\/1806689.1806769"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/nav.10092"},{"key":"R10","unstructured":"F. Eisenbrand, F. Grandoni, T. Rothvo\u00df, and G. Sch\u00e4fer,\n                      Approximating connected facility location problems via random facility sampling and core detouring\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 1174\u20131183."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol, S. Rao, and K. Talwar,\n                      A tight bound on approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 448\u2013455.","DOI":"10.1145\/780542.780608"},{"key":"R12","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , Freeman, San Francisco, CA, 1979."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"V. Goyal, A. Gupta, S. Leonardi, and R. Ravi,\n                      Pricing tree access networks with connected backbones\n                      , in Proceedings of the European Symposium on Algorithms, Lecture Notes in Comput. Sci. 4698, Springer, New York, 2007, pp. 498\u2013509.","DOI":"10.1007\/978-3-540-75520-3_45"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. Gupta and A. Kumar,\n                      A constant-factor approximation for stochastic Steiner forest\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2009, pp. 659\u2013668.","DOI":"10.1145\/1536414.1536504"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Gupta, A. Kumar, M. P\u00e1l, and T. Roughgarden,\n                      Approximation via cost-sharing: A simple approximation algorithm for the multicommodity rent-or-buy problem\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2003, pp. 606\u2013617.","DOI":"10.1109\/SFCS.2003.1238233"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236458"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Gupta, A. Kumar, and T. Roughgarden,\n                      Simpler and better approximation algorithms for network design\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365\u2013372.","DOI":"10.1145\/780542.780597"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"A. Gupta and M. P\u00e1l,\n                      Stochastic Steiner trees without a root\n                      , in Proceedings of the International Colloquium on Automata, Languages and Programming, Lisbon, Portugal, 2005, pp. 1051\u20131063.","DOI":"10.1007\/11523468_85"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A. Gupta, M. P\u00e1l, R. Ravi, and A. Sinha,\n                      Boosted sampling: Approximation algorithms for stochastic optimization\n                      , in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 417\u2013426.","DOI":"10.1145\/1007352.1007419"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"A. Gupta, R. Ravi, and A. Sinha,\n                      An edge in time saves nine: LP rounding approximation algorithms\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2004, pp. 218\u2013227.","DOI":"10.1109\/FOCS.2004.11"},{"key":"R22","unstructured":"N. Immorlica, D. Karger, M. Minkoff, and V. S. Mirrokni,\n                      On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2004, pp. 691\u2013700."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"A. Kumar, A. Gupta, and T. Roughgarden,\n                      A constant factor approximation algorithm for the multicommodity rent-or-buy problem\n                      , in Proceedings of the IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2002, pp. 333\u2013344.","DOI":"10.1109\/SFCS.2002.1181956"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0673-5"},{"key":"R25","unstructured":"G. Robins and A. Zelikovsky,\n                      Improved Steiner tree approximation in graphs\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2000, pp. 770\u2013779."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217860"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.02.005"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"A. van Zuylen,\n                      Deterministic sampling algorithms for network design\n                      , in Proceedings of the European Symposium on Algorithms, Lecture Notes in Comput. Sci. 5193, Springer, New York, 2008, pp. 830\u2013841.","DOI":"10.1007\/978-3-540-87744-8_69"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090767108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:06Z","timestamp":1787337246000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090767108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":28,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090767108"],"URL":"https:\/\/doi.org\/10.1137\/090767108","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}