A 2-approximation algorithm for the directed multiway cut problem
Joseph Seffi Naor, Leonid Zosin · 2002
A directed multiway cut separates a set of terminals s/sub 1/,...,s/sub /spl kappa// in a directed capacitated graph G=(V, E). Finding a minimum capacity directed multiway cut is an NP-complete problem. We give a polynomial-time algorithm that achieves an approximation factor of 2 for this problem. This improves the result of Garg, Vazirani and Yannakakis (1994) who gave an algorithm that achieves an approximation factor of 2 log /spl kappa/. Our approximation algorithm uses a novel technique for relaxing a multiway flow function in order to find a directed multiway cut. It also implies that the integrality gap of the linear program for the directed multiway cut problem is at most 2.