Approximating Steiner Forest and GW Primal-Dual Approach
The GW primal-dual approach for solving Steiner forest problems involves minimizing costs while ensuring certain connectivity constraints are met. Violated sets, primal and dual formulations, and increasing dual values play key roles in this approximation algorithm.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Approximating Steiner forest and other similar problems Based on a paper by Goemans and Williamsson
The GW primal dual. For Steiner forest the input is a series of pairs {si,ti } with costs c(e) on the edges. We want a minimum cost solution so that si,ti will be in the same connected component. The dual is based on the following: Consider any set S that contains exactly one of sior ti. These are called violated sets. Let A be the collection of violted sets.
Violated sets Let a,b be a pair that needs to be connected in the input. A set S is violated for a,b if a S and b S. A set S is violated, if it is violated for some pair.
Primal Minimze c(e) xe So that e (S)xS 1, for every violated S yS 0
The dual Maximize yS So that S A, e (S)yS c(e) yS 0
Increasing the duals of violated sets The algorithm maintains a dual feasible solution. We raise the dual values ySof all maximal violated sets at the same rate until a dual inequality for an edge e. Namely: S A, e (S)yS=c(e) All edges for which equality holds are added to the solution.
Say that we stopped when all the of violates sets increase by Each violated set dual value was increased by . Consider the edges added namely edges so that S A, e (S)yS=c(e) Changing sum order for every e for all S so that e (S), ySwas increases by
The portion of the lower bound we charge Say that there are a violated sets. The lower bound increases the dual of every violated set by the same, namely by some . The portion of the lower bound we charge against is a . Since the violated sets appear in the lower bound and each one of these a sets ySwas increased by .
The increase in the dual Increasing S by implies increasing all xe for the edges (S) (namely edges leaving S) by f h x e g
The increase in the dual Because S belongs to the inequality of every edge in (S). And in this case by 6 f h x e g
The increase in the dual We denote the number of edges leaving S by d(S). The dual increased by the sum of over all S of d(S) f h x e g
Making the edges a forest on violated and non violated sets We can (reverse) delete edges and keep connectivity. Hence the edges chosen and not deleted form a forest on violated and non violated sets. The increase in our dual is by S Ad(S) with d(S) the number of edges leaving S. This needs to be compared to a
The average degree The thing that determines the ratio is therefore d(s)/a namely, the average degree of violated sets. For this it is useful to note that leaves are violated sets. If a leaf is not violated, the unique edge can be removed and the solution is still feasible.
The average degree of violated sets The sum of degrees in this tree is 2k-2 with k the number of violated and non violated sets, and so the average is 2-2/k. Now, what happens when we ignore non volated sets? Since each non violated set is not a leaf it s degree is at least 2 namely above the average. Hence removing non violated sets can only decrease the average. And so the average of violated sets is at most 2-2/k. Since the sum of degrees of violated sets is the contribution to the dual, and a is the part of the lower bound we charge, the approximation ratio is at most 2- 2/k
What did we do? The cost of edges were broken into uniform values with different fixed . For every such increase we show that the increase in the dual of of violated sets is at least the increase in the dual. Hence each event ratio 2. Hence ratio 2.
