Improving the integrality gap for multiway cut

Abstract: In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminals, and the goal is to partition the vertices into k 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. Assuming the unique games conjecture, the approximability of this problem coincides with the integrality gap of an LP-relaxation, known as the CKR relaxation. The CKR relaxation embeds the graph into a (k-1)-dimensional simplex. For arbitrary k, the best-known upper bound on the integrality gap is 1.2965 while the previous best-known lower bound on the integrality gap was 1.2. In a recent work, we improved the lower bound to 1.20016 by constructing a 3-dimensional simplex instance. In this talk, I will present the main ideas underlying the construction and the analysis of this instance.

Based on joint work with Kristof Berczi, Tamas Kiraly, and Vivek Madan.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

---

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.

---