{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:24:58Z","timestamp":1787340298959,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>The natural relaxation for the group Steiner tree problem, as well as for its generalization, the directed Steiner tree problem, is a flow\u2010based linear programming relaxation. We prove new lower bounds on the integrality ratio of this relaxation. For the group Steiner tree problem, we show that the integrality ratio is $\\Omega(\\log^2 k)$, where k denotes the number of groups; this holds even for input graphs that are hierarchically well\u2010separated trees, introduced by Bartal [in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 184\u2013193], in which case this lower bound is tight. This also applies for the directed Steiner tree problem. In terms of the number n of vertices, our results for the directed Steiner problem imply an $\\Omega(\\frac{\\log^2 n}{(\\log \\log n)^2})$ integrality ratio. For both problems, these are the first lower bounds on the integrality ratio that are superlogarithmic in the input size. This exhibits, for the first time, a relaxation of a natural optimization problem whose integrality ratio is known to be superlogarithmic but subpolynomial. Our results and techniques have been used by Halperin and Krauthgamer [in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585\u2013594] to show comparable inapproximability results, assuming that NP has no quasi\u2010polynomial Las Vegas algorithms. We also show algorithmically that the integrality ratio for the group Steiner tree problem is much better for certain families of instances, which helps pinpoint the types of instances (parametrized by optimal solutions to their flow\u2010based relaxations) that appear to be most difficult to approximate.<\/jats:p>","DOI":"10.1137\/s0097539704445718","type":"journal-article","created":{"date-parts":[[2007,2,21]],"date-time":"2007-02-21T16:07:26Z","timestamp":1172074046000},"page":"1494-1511","source":"Crossref","is-referenced-by-count":18,"title":["Integrality Ratio for Group Steiner Trees and Directed Steiner Trees"],"prefix":"10.1137","volume":"36","author":[{"given":"Eran","family":"Halperin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nan","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,2,5]]},"reference":[{"key":"BAR96","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      Probabilistic approximation of metric spaces and its algorithmic applications\n                      , in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 184\u2013193.","DOI":"10.1109\/SFCS.1996.548477"},{"key":"BAR98","doi-asserted-by":"crossref","unstructured":"Y. Bartal,\n                      On approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"BBM01","doi-asserted-by":"crossref","unstructured":"Y. Bartal, B. Bollob\u00e1s, and M. Mendel,\n                      A Ramsey\u2010type theorem for metric spaces and its applications for metrical task systems and related problems\n                      , in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 396\u2013405.","DOI":"10.1109\/SFCS.2001.959914"},{"key":"BM04","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433122"},{"key":"CCC99","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"CCGG98","doi-asserted-by":"crossref","unstructured":"M. Charikar, C. Chekuri, A. Goel, and S. Guha,\n                      \n                        Rounding via trees: Deterministic approximation algorithms for group Steiner trees and\n                        k\n                        \u2010median\n                      \n                      , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 114\u2013123.","DOI":"10.1145\/276698.276719"},{"key":"CEK06","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.07.010"},{"key":"CGH05","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082038"},{"key":"FEI98","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"FRT04","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"GKR00","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"GS06","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a003"},{"key":"HK03","doi-asserted-by":"crossref","unstructured":"E. Halperin and R. Krauthgamer,\n                      Polylogarithmic inapproximability\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585\u2013594.","DOI":"10.1145\/780542.780628"},{"key":"JAN90","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010209"},{"key":"KRS01","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00161-2"},{"key":"KRS02","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10038"},{"key":"LY94","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"MR95","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"RS97","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra,\n                      A sub\u2010constant error\u2010probability low\u2010degree test, and a sub\u2010constant error\u2010probability PCP characterization of NP\n                      , in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 475\u2013484.","DOI":"10.1145\/258533.258641"},{"key":"SRI01","unstructured":"A. Srinivasan,\n                      New approaches to covering and packing problems\n                      , in Proceedings of the Twelfth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, 2001, pp. 567\u2013576."},{"key":"ZK02","unstructured":"L. Zosin and S. Khuller,\n                      On directed Steiner trees\n                      , in Proceedings of the Thirteenth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, 2002, pp. 59\u201363."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539704445718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:28:58Z","timestamp":1787336938000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539704445718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/S0097539704445718"],"URL":"https:\/\/doi.org\/10.1137\/s0097539704445718","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}