Improving the Integrality Gap for Multiway Cut
share
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, 2014] while the best known inapproximability factor is 1.2 due to [Angelidakis, Makarychev and Manurangsi, 2017]. 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 byproducts from our proof technique is a generalization of a result on Sperner admissible labelings due to [Mirzakhani and Vondrák, 2015] that might be of independent combinatorial interest.
READ FULL TEXT
