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

YouTube

Simple and Fast Rounding Algorithms for Directed and Node Weighted Multiway Cut

Hausdorff Center for Mathematics via YouTube

Overview

Explore a lecture on advanced graph theory algorithms focusing on simple and fast rounding techniques for directed and node-weighted multiway cut problems. Delve into the intricacies of the multiway cut problem, where the goal is to remove a minimum-weight subset of edges or nodes to disconnect terminals in a graph. Examine the 2-approximation for directed multiway cut (Dir-MC) and the 2(1-1/k) approximation for node-weighted multiway cut (Node-MC). Discover extremely simple, near linear-time rounding algorithms that achieve the same approximation ratios using a natural distance-based LP relaxation. Learn about the integrality gap of the LP relaxation for Dir-MC in directed planar graphs with two terminals. Gain insights from this joint work with Chandra Chekuri, presented as part of the Hausdorff Trimester Program on Combinatorial Optimization.

Syllabus

Vivek Madan: Simple and fast rounding algorithms for directed and node weighted multiway cut

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of Simple and Fast Rounding Algorithms for Directed and Node Weighted 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.