ECCC-Report TR07-120https://eccc.weizmann.ac.il/report/2007/120Comments and Revisions published for TR07-120en-usWed, 05 Dec 2007 12:46:40 +0200
Paper TR07-120
| Improved approximation algorithms for directed Steiner forest |
Sharon Feldman,
Guy Kortsarz,
Zeev Nutov
https://eccc.weizmann.ac.il/report/2007/120We 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.
Wed, 05 Dec 2007 12:46:40 +0200https://eccc.weizmann.ac.il/report/2007/120