Improved approximation algorithms for Directed Steiner Forest

Moran Feldman, Guy Kortsarz, Zeev Nutov

Research output: Contribution to journalArticle

27 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×V of ordered node pairs, and an integer k≤|D|, find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs (s,t) D. When k=|D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: Õ(k2/3) for k-DSF by Charikar et al. (1999) [6], and O(k1/2+ε) for DSF by Chekuri et al. (2008) [7]. Our main result is achieving the first sub-linear in terms of n=|V| approximation ratio for DSF. Specifically, we give an O(.min{n4/5,m2 /3})-approximation scheme for DSF. For k-DSF we give a simple greedy O(k1/2+ε)-approximation algorithm. This improves upon the best known ratio Õ(k2/3) by Charikar et al. (1999) [6], and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 [18]). This algorithm uses a new structure called start-junction tree which may be of independent interest.

Original languageEnglish (US)
Pages (from-to)279-292
Number of pages14
JournalJournal of Computer and System Sciences
Volume78
Issue number1
DOIs
StatePublished - Jan 1 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Approximation algorithm
  • Directed Steiner Forest

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

  • Cite this