Reference no: EM133121876

Question 1. Consider the following algorithm for the maximum cut problem, based on the technique of local search. Given a partition of V into sets, the basic step of the algorithm, called flip, is that of moving a vertex from one side of the partition to the other. The following algorithm finds a locally optimal solution under the flip operation, i.e., a solution which cannot be improved by a single flip.

The algorithm starts with an arbitrary partition of V. While there is a vertex such that flipping it increases the size of the cut, the algorithm flips such a vertex. (Observe that a vertex qualifies for a flip if it has more neighbors in its own partition than in the other side.) The algorithm terminates when no vertex qualifies for a flip. Show that this algorithm terminates in polynomial time, and achieves an approximation guarantee of 1/2.

Question 2. The hardness of the Steiner tree problem lies in determining the optimal subset of Steiner vertices that need to be included in the tree. Show this by proving that if this set is provided, then the optimal Steiner tree can be computed in polynomial time.

Question 3. Give an approximation factor preserving reduction from the set cover problem to the following problem, thereby showing that it is unlikely to have a better approximation guarantee than O(log n).

Question 4. Show that Algorithm 4.3 can be used as a subroutine for finding a k-cut within a factor of 2 - 2/k of the minimum k-cut. How many subroutine calls are needed?

Question 5. Algorithm - Multiway cut

1. For each i = 1,....,k, compute a minimum weight isolating cut for si, say C_i.

2. Discard the heaviest of these cuts, and output the union of the rest, say C.