https://illinois.zoom.us/j/85054031332?pwd=d1hRNS9wTlVFRmtpTzZmQkxld1YzZz09
Meeting ID: 850 5403 1332
Passcode: theorycs
—————
Title: ℓ_p-norm Multiway Cut
—————
Abstract:
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.