Under Construction
(GSF) Generalized Steiner Forest
Instance: A graph G=(V,E), a weight W(e)>=0 for each e in E.
A collection of terminal sets T={T1,T2,...,Tt},
each a subset of V. A subset C of the edges E
Solution: A generalized steiner forest (GSF) i.e.
for each T_i, and for every pair of terminals x,y in T_i,
there exists a path in C connecting x and y
Measure : W(C) (i.e. Sum {W(e): e in C}).
+-----------------------------------------------------------------+
| The "Local-Ratio Theorem" (oriented for GSF) |
+-----------------------------------------------------------------+
| If C is 2-approximation GSF w.r.t the weight function W1 |
| and C is 2-approximation GSF w.r.t the weight function W2 |
| then C is 2-approximation GSF w.r.t the weight function W1+W2 |
+-----------------------------------------------------------------+
Our objective is to find a MINIMAL-GSF C, i.e.
C is an GSF, but for each e in C: C-{e} is not GSF.
Observations1: If Ti intersects Tj than we can replace them
by there union.
Observations2: If W({x,y})=0 We can shrink x and y, use Observation1
if needed and proceed recursively, after recursion
in back, "UN-shrink" xy and add it to the forest
if does not disturb minimality.
Local Ratio Step:
Define W1 to be epsilon HOMOGENEOUS, i.e.
for all e in E: W1(e) = epsilon*terminal_degree(e)
Where: terminal degree e is the number of e's terminal endpoints.
Q1: Every MINIMAL-GSF is 2-approximations w.r.t W1. Why?
Solve recursively for W2=W-W1 and get 2-approximate GSF, modify
it to be minimal w.r.t the edges e s.t. W(e)>0 to get MINIMAL-GSF C.
C is 2-approx w.r.t. W1 (see Q1)
C is 2-approx w.r.t. W2 (By induction Hyp.)
therefore by the Local-Ratio Theorem:
C is 2-approx w.r.t. W (=W1+(W-W1))
p.s. Sanjeev Khanna suggests the following simpler weight
function: W1(e) = epsilon iff e adjacent to any terminal.
Now: t<=W1(C)<=2*t is trivial.