Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes

Joshua Brakensiek, Neng Huang, Aaron Potechin +1

The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and $k$ designated terminals. The goal is to partition the vertices of the grap…