Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

LP-Norm Multiway Cut

Hausdorff Center for Mathematics via YouTube

Overview

Explore the lp-norm multiway cut problem in graph theory through this 31-minute lecture by Karthik Chandrasekaran from the Hausdorff Center for Mathematics. Delve into the intricacies of this unified generalization of min-sum and min-max multiway cut problems, where the goal is to partition a weighted undirected graph's vertex set into k parts, each containing one terminal, while minimizing the lp-norm of the cut values. Examine hardness results, integrality gap, and learn about an O(log^2 n)-approximation for this problem. Gain insights into the collaborative work with Weihang Wang on this important graph partitioning challenge.

Syllabus

Karthik Chandrasekaran: lp-Norm Multiway Cut

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of LP-Norm Multiway Cut

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.