Scribe: Arnaud de Mesmay
This lecture is about Multiway-Cut and Multi-Cut, which are good illustrations of the techniques used to design approximation algorithms using LP relaxations.
The Min-Cut problem is the following problem : the input is a graph and two vertices and and the goal is to find the cheapest cut separating and . As we will see in the next section, it is the Multiway-Cut problem for k=2.
Min-Cut is solvable in polynomial time using classic algorithms (flows..) but we will see here a way to solve it using linear programming.
The first step is to express the problem as an Integer Program (IP)
There are two claims to prove in order to get a polynomial time algorithm.
Claim: There is a separation oracle for the LP relaxation of the above IP (we need it as the number of constraints is exponential)
Proof: The separation algorithm is just Dijkstra’s algorithm to compute a shortest path from to in the graph where edge has length .
Claim: the LP relaxation has an integral optimal solution.
Proof: Let denote the optimal solution of the LP relaxation. Consider distances from to graph vertices in the shortest path metric (using the as edge lengths). Pick a random uniformly in the open interval . Partition the graph into two sets, , and . That defines a random integer cut (convex combination of integer cuts). The expected value of this cut:
Hence the optimal solution is a convex combination of integral solutions, thus these integral solutions are optimal too, which concludes the proof.
2. Multiway cut
Input: graph with edge costs , and terminals, vertices . Output: cheapest set of edges disconnecting the ‘s from one another. For , this problem is NP-hard.
Theorem 1 There is a 3/2 approximation.
Proof: The idea is still the same, we use a LP relaxation and then round it.
Equivalently, the output is a partition of into parts, where belongs to part , and the cost is the cost of edges between different parts. An IP for the Multiway-Cut problem is :
The idea behind this IP is that means that the vertex is in the partition which contains . The constraints force these to define a partition of , and then the cost of the multiway cut is easily seen to equal the expression we try to minimize.
Observing that where and that where the 1 is in the ith position, an equivalent representation of the LP relaxation is :
where and the 1 in is in position .
For example, for , this LP gives an embedding of in the equilateral triangle with at the three corners.
Rounding: Similarly as for Min-Cut, the idea to round it is to pick a random and partition with the balls around of radius .
The rounding algorithm is the following :
- Pick uniformly at random.
- Pick permutation of uniformly at random.
- For ; put in region the vertices within distance of that have not yet been put elsewhere. Put everyone else in region . The gives a partition, i.e. a multicut.
Analysis: The expected cost of the output cut is
Up to relabeling, let be the one among that minimizes .
But for , precedes in permutation with probability , and comes after with probability (because is random). Also note that if comes after in , then ‘s iteration cannot be responsible of separating from (because of the “definition” of ).
We also have
where the last inequality follows from the constraints in the LP.
because the probability of cutting for is the probability that falls between and . Now recall that is never cut by when comes after and note, as for that the probability of cutting at step is bounded by . this gives
Last claim :
Proof: Left as an Exercise.
Now , thus the expected value of the output is at most of the value of the LP.
Input: graph with edge costs , and terminal pairs, pairs of vertices . Output: cheapest set of edges disconnecting every from .
This problem is NP-hard for small ( ? ?)
Theorem 2 There is an approximation.
Proof: As before, it is all about finding the right LP and rounding it.
(LP relaxation) We use the following one :
(Rounding : ) For going from 1 to k: if is not yet separated from , then take a ball of radius around , where is chosen to minimize , with
(it is different for each !). Add as a new part of the partition of that we are constructing, and remove from .
(Analysis:) Feasibility: since , by the LP constraints on we can be sure that no couple will be in a ball corresponding to for , so the output is a feasible multicut.
Cost: note that , so , and so . Thus the ball chosen has , where we define . It only remains to use the Mean Value Theorem for .
We have and , hence the Mean Value Theorem gives
Thus each ball added to the partition during iteration increases the cost of the multicut by . Altogether, the final multicut has cost at most
Setting proves the Theorem.