TR07-120 Authors: Sharon Feldman, Guy Kortsarz, Zeev Nutov

Publication: 5th December 2007 12:46

Downloads: 1234

Keywords:

We consider the k-Directed Steiner Forest} (k-dsf) problem:

given a directed graph G=(V,E) with edge costs, a collection D subseteq V \times V

of ordered node pairs, and an integer k leq |D|, find a minimum cost subgraph

H of G

that contains an st-path for (at least) k pairs (s,t) \in D.

When k=|D|, we get the Directed Steiner Forest dsf problem.

The best known approximation ratios for these problems are:

tilde O(k^{2/3}) for k-dsf by Charikar et.~al \cite{CCC}, and

O(k^{1/2 + epsilon) for dsf by Chekuri et.~al \cite{CEGS}.

We improve these approximation ratios as follows.

For dsf we give an tilde O(n^{4/5 + \epsilon)-approximation scheme

using a novel LP-relaxation that seeks to connect pairs with ''cheap'' paths.

This is the first sub-linear (in terms of n=|V|) approximation ratio for the problem;

all previous algorithm had ratio Omega(n^{1+epsilon}).

For k-dsf we give a simple greedy O(k^{1/2 + epsilon})-approximation algorithm.

This improves the best known ratio \tilde O(k^{2/3}) by Charikar et. al \cite

{CCC}, and

(almost) matches in terms of k the best ratio known for the undirected variant

\cite{GHNR}.

Even when used for the particular case of dsf, our algorithm favorably compares

to the one of \cite{CEGS}, which repeatedly solves linear programs

and uses complex space and time consuming transformations.

Our algorithm is much simpler and faster, since it essentially reduces k-dsf

to a variant of the Directed Steiner Tree problem.

The simplification is due to a new notion of ``junction star-tree'' -- a union of an in-star

and an out-branching having the same root, which is of independent interest.