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.