Computer Science Speakers Series

Back to Listing

Theory Seminar: Weihang Wang, "ℓ_p-norm Multiway Cut"

Event Type
Chandra Chekuri
wifi event
Nov 8, 2021   10:00 am  
Originating Calendar
Computer Science Speakers Calendar

Meeting ID: 850 5403 1332

Passcode: theorycs



Title: ℓ_p-norm Multiway Cut



We introduce and study ℓ_p-norm multiway cut: the input here is an undirected graph with non-negative edge weights along with k terminals and the goal is to find a partition of the vertex set into k parts each containing exactly one terminal to minimize the ℓ_p-norm of the cut values of the parts. In this talk, we will discuss the background on various objectives for multiway cut problems. We will introduce a convex relaxation for ℓ_p-norm multiway cut and see an example that has an integrality gap of Omega(k^{1-1/p}). The focus of the talk will be on two approximation algorithms for ℓ_p-norm multiway cut that share generalizable similarities. The first one relies on the isolating cuts approach and achieves an approximation factor of O(k^{1-1/p}); the second one relies on multiplicative weights update and achieves an approximation factor of O(log^2 n).


Joint work with Karthik Chandrasekaran.

link for robots only