Improving the integrality gap for multiway cut

DOI10.1007/978-3-030-17953-3_9MaRDI QIDQ5919382zbMATH OpenOpenAlexFDO

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

Publication date 6 February 2020

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.09735, http://real.mtak.hu/113033/1/egres-19-04.pdf

zbMATH Keywords

approximationcombinatorial optimizationintegrality gapmultiway cut

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: 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 $kge3$ is APX-hard. For arbitrary $k$, the best-known approximation factor is $1.2965$ due to [Sharma and Vondr'{a}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 ingredients of our proof technique is a generalization of a result on emph{Sperner admissible labelings} due to [Mirzakhani and Vondr'{a}k, 2015] that might be of independent combinatorial interest.

Recommendations

• Improving the integrality gap for multiway cut
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• scientific article; zbMATH DE number 1775387
• An improved approximation algorithm of MULTIWAY CUT.
• An improved parameterized algorithm for the multicut problem
• Strengthening Gomory Mixed-Integer Cuts
• scientific article; zbMATH DE number 1787231
• Reduce-and-Split cuts: improving the performance of mixed-integer Gomory cuts

Cited in

(5)

• Geometric multicut: shortest fences for separating groups of objects in the plane
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• Local distribution and the symmetry gap: approximability of multiway partitioning problems
• Improving the integrality gap for multiway cut
• Towards overcoming the undercutting problem

This page was built for publication: Improving the integrality gap for multiway cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919382)