On directed Steiner trees

Leonid Zosin, Samir Khuller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

91 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages59-63
Number of pages5
ISBN (Electronic)089871513X
StatePublished - Jan 1 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Conference

Conference13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
CountryUnited States
CitySan Francisco
Period1/6/021/8/02

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'On directed Steiner trees'. Together they form a unique fingerprint.

Cite this