Improved approximating algorithms for Directed Steiner Forest

Moran Feldman, Guy Kortsarz, Zeev Nutov

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

21 Scopus citations

Abstract

We consider the k-Directed Steiner Forest (k-DSF) problem: given a directed graph G = (V, E) with edge costs, a collection D ⊆ V x V of ordered node pairs, and an integer k ≤ |D|, find a min-cost subgraph H of G that contains an st-path for (at least) kc pairs (s, t) ∈ D. When k = |D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: Õ(k 2/3) for k-DSF by Charikar et al. [2], and O(k 1/2+ε) for DSF by Chekuri et al. [3]. For DSF we give an O(n ε·mm{n 4/5, m 2/3})-approximation scheme using a novel LP-relaxation seeking to connect pairs via "cheap" paths. This is the first sublinear (in terms of n = |V|) approximation ratio for the problem. For k-DSF we give a simple greedy O(k 1/2+ε)-approximation scheme, improving the best known ratio Õ(k 2/3) by Charikar et al. [2], and (almost) matching, in terms of k, the best ratio known for the undirected variant [11]. Even when used for the particular case DSF, our algorithm favorably compares to the one of [3], which repeatedly solves linear programs, and uses complex time and space consuming transformations.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages922-931
Number of pages10
StatePublished - 2009
Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
Duration: Jan 4 2009Jan 6 2009

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityNew York, NY
Period1/4/091/6/09

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Improved approximating algorithms for Directed Steiner Forest'. Together they form a unique fingerprint.

Cite this