TY - JOUR T1 - Approximation algorithms for the covering Steiner problem JF - Random Structures & Algorithms Y1 - 2002 A1 - Konjevod,Goran A1 - Ravi,R. A1 - Srinivasan, Aravind AB - The covering Steiner problem is a generalization of both the k-MST and the group Steiner problems: given an edge-weighted graph, with subsets of vertices called the groups, and a nonnegative integer value (called the requirement) for each group, the problem is to find a minimum-weight tree spanning at least the required number of vertices of every group. When all requirements are equal to 1, this becomes the group Steiner problem, while if there is only one group which contains all vertices of the graph the problem reduces to k-MST with k equal to the requirement of this unique group. We discuss two different (but equivalent) linear relaxations of the problem for the case when the given graph is a tree and construct polylogarithmic approximation algorithms based on randomized LP rounding of these relaxations. By using a probabilistic approximation of general metrics by tree metrics due to Bartal, our algorithms also solve the covering Steiner problem on general graphs with a further polylogarithmic worsening in the approximation ratio. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:465–483, 2002 VL - 20 SN - 1098-2418 UR - http://onlinelibrary.wiley.com/doi/10.1002/rsa.10038/abstract?systemMessage=Wiley+Online+Library+will+be+disrupted+17+March+from+10-14+GMT+%2806-10+EDT%29+for+essential+maintenance CP - 3 M3 - 10.1002/rsa.10038 ER -