TY - GEN

T1 - On directed Steiner trees

AU - Zosin, Leonid

AU - Khuller, Samir

PY - 2002/1/1

Y1 - 2002/1/1

N2 - The directed Steiner tree problem is the following: given a directed graph G = (V, E) with weights on the edges, a set of terminals S C V, and a root vertex r, find a minimum weight out-branching T rooted at r, such that all vertices in S are included in T. This problem is known to be NP-hard. Recently, non-trivial polynomial time approximation algorithms have been developed for this problem with worst case approximation guarantees of O(kϵ) for any fixed ϵ > 0. We consider a natural LP relaxation of this problem. Using a dual formulation we construct a simple deterministic (D + l)-approximation algorithm for a special case when the subgraph induced by V \ S is a tree with depth D (for example, this can be shown to include the group Steiner tree problem as a special case, by the loss of poly-log factors in the approximation guarantee). We also show that this LP has an integrality gap of φ(y√k) for the general problem.

AB - The directed Steiner tree problem is the following: given a directed graph G = (V, E) with weights on the edges, a set of terminals S C V, and a root vertex r, find a minimum weight out-branching T rooted at r, such that all vertices in S are included in T. This problem is known to be NP-hard. Recently, non-trivial polynomial time approximation algorithms have been developed for this problem with worst case approximation guarantees of O(kϵ) for any fixed ϵ > 0. We consider a natural LP relaxation of this problem. Using a dual formulation we construct a simple deterministic (D + l)-approximation algorithm for a special case when the subgraph induced by V \ S is a tree with depth D (for example, this can be shown to include the group Steiner tree problem as a special case, by the loss of poly-log factors in the approximation guarantee). We also show that this LP has an integrality gap of φ(y√k) for the general problem.

UR - http://www.scopus.com/inward/record.url?scp=84968884503&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84968884503&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84968884503

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 59

EP - 63

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -