BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Karthekeyan Chandrasekaran (UIUC) DTSTART:20210526T153000Z DTEND:20210526T160000Z DTSTAMP:20260414T235649Z UID:MIP2021/13 DESCRIPTION:Title: Improving the integrality gap for multiway cut\nby Karthekeyan Chandr asekaran (UIUC) as part of Mixed Integer Programming Workshop 2021\n\n\nAb stract\nIn the multiway cut problem\, we are given an undirected graph wit h 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 ter minal so that the total weight of the edges crossing the partition is mini mized. 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 arbitra ry k\, the best-known upper bound on the integrality gap is 1.2965 while t he previous best-known lower bound on the integrality gap was 1.2. In a re cent work\, we improved the lower bound to 1.20016 by constructing a 3-dim ensional simplex instance. In this talk\, I will present the main ideas un derlying the construction and the analysis of this instance.\n\nBased on j oint work with Kristof Berczi\, Tamas Kiraly\, and Vivek Madan.\n LOCATION:https://researchseminars.org/talk/MIP2021/13/ END:VEVENT END:VCALENDAR