An improved approximation algorithm for multiway cut

Abstract

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.~y CUT 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<L c; 3'