LP-Norm Multiway Cut

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.

Karthik Chandrasekaran: lp-Norm Multiway Cut