Multiway cut

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+sqrt(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 and was presented at STOC'14.