Ankit Sharma: Multiway Cut

Multiway cut is a generalization of the min-cut problem to one with more than two terminals. Theoretically, given a set of terminals in a graph, the objective is to assign each vertex to some terminal while minimizing the number of ‘cut’ edges – edges whose end points are assigned to different terminals. The special case of this problem with two terminals is the “max-flow/min-cut problem”. With three or more terminals, the problem is NP hard.

The problem has a rich history in approximation algorithms. Starting with a 2-approximation by Dahlhaus et al. in 1994, the problem received a major improvement in a paper by Calinescu et al., where they presented a relaxation of the problem, and a 1.5 approximation to it. It was subsequently shown that it is UGC hard to beat the integrality gap of this relaxation. The rounding schemes to the relaxation were also subsequently improved, and in a recent result, Buchbinder et al. in STOC 2013, introduced a new rounding scheme that gave a 1.32388 approximation. In a work with Jan Vondrak, we first present the best combination of rounding schemes used by Buchbinder et al., and show that it is limited to achieving a factor of 1.30902 (=(3+5√)/4). We then introduce a new rounding scheme and show that the new combination of rounding schemes achieves an approximation factor close to 1.2965. Under UGC, it is NP hard to go below 1.14.

This is a joint work with Jan Vondrak.

Bio: Ankit Sharma is a graduate student at Carnegie Mellon University. He is advised by Avrim Blum and Anupam Gupta. His research focuses on approximation algorithms and algorithmic game theory.