An improved approximation algorithm for multiway cut
Gruiă Cälinescu, Howard J. Karloff, Yuval Rabani · 1998
Given an undirected graph wit.h edge co&s and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest.~iULTIW.~yCUT is the problem of finding a multiway cut of minimum cost..Previously, a very simple combinatorial algorithm due to Dahlhaus, Johnson, Papadimitriou, Seymour, and %nnr-lkakis gave a performance guarantee of 2 (1 -$), In this paper, we present a new linear programming rslax-&ion for ~fULTIW&Y CUT and a new approximation dgorithm based on it.The algorithm breaks the threshold of 2 for approximating MULTIWAY CUT, achieving a performance ratio of at.most 1.5 -$.This improves the previous result for every value of k.In particular, for k = 3 we get a ratio ofZ