TITLE: Approximating k-MultiCut Problem
SPEAKER: Mohit Singh
WHEN: December 8, 4-5:30pm
WHERE: PPB 300
ABSTRACT: Given an undirected graph, a set of $t$ pairs of vertices, the multi-cut problem is to find the minimum set of edges to remove which separate all pairs. The $k$-multicut problem is a generalization of the multicut problem in which one is given a target $k \leq t$ and asked to remove only $k$ pairs. We use techiniques from combinatorial optimization: Lagrangian relaxation and Total unimodularity, to obtain constant factor approximation for the $k$-multicut problem on trees. This also leads to $O(log^2 n log logn)$-approximation for the $k$-multicut problem on general graphs, where $n$ is the number of vertices in the graph. We also give bicriterion approximation algorithm for the $k$-multicut problem. Our techniques also give a simple $2$-approximation algorithm for the multicut problem on trees matching the best known algorithm of Garg, Vazirani and Yannakakis’94.
Joint Work with Viswanath Nagarajan and Daniel Golovin. To appear in SODA’06.
