Uran.donetsk.ua

18.434: Seminar in Theoretical Computer Science Recall from last time the multiway cut problem: given a graph with weightededges and a set of terminals S = {s1, s2, . . . , sk} ⊆ V , find the minimumweight set of edges E ⊆ E which, when removed, leaves all terminals sep-arated from all other terminals. Last time, a combinatorial algorithm wasgiven with an approximation factor of 2 − 2 . This lecture will show a ran- domized linear programming algorithm with an approximation factor of 3 .
k denote the k − 1 dimensional simplex; that is, the surface in R the ith coordinate of x. The LP relaxation will map each vertex of G to apoint in ∆k. Each terminal will be mapped to a different unit vector. Letxv represent the point to which vertex v is mapped. Define the length of anedge (u, v) to be An integer solution to this relaxation maps each vertex of G to a unit vector. Each vertex represents a component of the graph after E is removed.
Edges within one component have length 0, and edges between components(i.e., those in E ) have length 1. The function being minimized is thereforeequal to the cost of E .
It is not clear that the above is a true linear program, due to the absolute values. However, this is not a problem. To create an equivalent true linearprogram, replace the first constraint with: Because of the minimization, any optimal solution must satisfy xiuv) = We may assume, without loss of generality, that for each edge (u, v) ∈ E, xu and xv differ in at most two coordinates.
Proof. Along any edge (u, v) where xu and xv differ in more than two co-ordinates, insert a new vertex w and replace (u, v) with (u, w) and (w, v).
Assign both (u, w) and (w, v) the same cost as (u, v). This does not changethe cost of the optimal integral solution.
Now consider the optimal fractional solution. Since d is a valid distance function, d(u, w) + d(w, v) ≥ d(u, v).
solution cannot decrease because of the addition of w. Now, let i be thecoordinate in which the difference between xi and xi is minimal (disregarding coordinates where xi = xi ). Without loss of generality assume xi < xi and let α = xi −xi . There must be a coordinate j such that xj ≥ xj +α. Consider the solution with xi = xi and xj = xj + α. All other coordinates of x equal to those of xv. This gives xw ∈ ∆k and d(u, v) = d(u, w) + d(w, v).
xv and xw differ in only two coordinates, and xw and xu differ in fewer coordinates than xu and xv. Repeated application of this process will give asolution with the same cost and with the desired property.
Take an optimal solution to the relaxation with edges whose endpoints differin at most two coordinates, and let OP T denote its cost.
(u, v) ∈ E|xi = xi . (Note that each edge will lie in two of these sets.) Define c(e)d(e). Without loss of generality, assume that W greatest of W1, . . . , Wk. Also define B(si, ρ) = v ∈ V |xi ≥ ρ.
The algorithm operates as follows. First, pick ρ at random in (0, 1) and an ordering σ from (1, 2, . . . , k − 1, k) and (k − 1, k − 2, . . . , 1, k). Thenpartition V into V1, . . . , Vk as follows. Proceed in the order given by σ. EachVi should contain all vertices in B(si, ρ) that have not already been assignedto a previous Vi. At the end, assign all unused vertices to Vk. The setsV1, . . . , Vk are the components after removing the cut, and edges betweenvertices in two different sets are in the cut.
1. Compute an optimal solution to relaxation.
2. Renumber the terminals so that Wk is largest among W1, . . . , Wk.
3. Pick uniformly at random ρ ∈ (0, 1) and σ ∈ (1, 2, . . . , k − 1, k), (k − 1, k − 2, . . . , 1, k).
4. For i = 1 to k − 1: Vσ(i) ← B(si, ρ) − 6. Let C be the set of edges that run between sets in the partition Let C be the cut produced by the algorithm, c(C) be the cost of C, and OP Tbe the cost of the optimal solution to the linear program. We will show thatE[c(C)], the expected value of c(C), is at most (1.5 − 1 ) × OP T .
Lemma 1. If e ∈ Ek, then Pr[e ∈ C] ≤ d(e).
Proof. The endpoints of E differ in coordinates i and k. Since Vk is deter-mined without considering the coordinates of the points left over, and allcoordinates except i and k are equal, the only way that endpoints u and vwill end up in different sets is if one (but not the other) is in Vi. This occursif and only if ρ is between xi and xi . This has probability d(e).
Lemma 2. If e ∈ E − Ek, then Pr[e ∈ C] ≤ 1.5d(e).
Proof. The endpoints of E, u and v, differ in coordinates i and j. Let β bethe interval [xj , xj ] and let α be the part of [xi , xi ] that does not overlap with β. u and v can each end up in either Vi, Vj, or Vk. Assume withoutloss of generality that α is closer to 0 than β. (If not, switching the values ofi and j makes it so.) u and v end up in different sets if and only if ρ ∈ β, orρ ∈ α and σ(i) < σ(j). Therefore Pr[e ∈ C] = |β| + |α| ≤ 1.5d(e) (because Theorem 1. E[c(C)] ≤ (1.5 − 1 ) × OP T .
i = 2 · OP T , and Wk was chosen to be the

Source: http://uran.donetsk.ua/~masters/2006/kita/papko/library/art9.pdf