An improved approximation algorithm for multiway cut

Given an undirected graph with edge costs and a subset of ii nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal From the rest. MULTIWAY CUT is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm duc to Dahlhaus, Johnson, Papadimitriou, Seymour, and Yannakakis gave a performance guarantee of 2(1 - 1/k). In this paper, we present a new linear programming relaxation for MULTIWAY Cur and a new approximation algorithm based on it. The algorithm breaks the threshold of 2 for approximating MULTIWAY CUT. achieving a performance ratio of at most 1.5 - 1/k. This improves the previous result for every value of k. In particular, for k = 3 we get a ratio of 7/6 < 4/3. (C) 2000 Academic Press.