Improving the Integrality Gap for Multiway Cut

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan


In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k>=3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák, while the best known inapproximability factor is 1.2 due to Angelidakis, Makarychev and Manurangsi. In this work, we improve on the lower bound to 1.20016 by constructing an integrality gap instance for the CKR relaxation.
A technical challenge in improving the gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial 3-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap. One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák that might be of independent combinatorial interest.

Bibtex entry:

AUTHOR = {B{\'e}rczi, Krist{\'o}f and Chandrasekaran, Karthekeyan and Kir{\'a}ly, Tam{\'a}s and Madan, Vivek},
TITLE = {Improving the Integrality Gap for Multiway Cut},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-04}

Last modification: 29.12.2020. Please email your comments to Tamás Király!