Simple and Fast Rounding Algorithms for Directed and Node Weighted Multiway Cut
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.