Computer Science Speakers Series

Back to Listing

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

Event Type
Seminar/Symposium
Sponsor
Chandra Chekuri
Location
https://illinois.zoom.us/j/85054031332?pwd=d1hRNS9wTlVFRmtpTzZmQkxld1YzZz09
Virtual
wifi event
Date
Nov 8, 2021   10:00 am  
Views
20
Originating Calendar
Computer Science Speakers Calendar

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.

link for robots only