An improved approximation algorithm for multiway cut

Given an undirected graph with edge costs and a subset of ii nodes called t erminals, a multiway cut is a subset of edges whose removal disconnects eac h 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 perfor mance guarantee of 2(1 - 1/k). In this paper, we present a new linear progr amming relaxation for MULTIWAY Cur and a new approximation algorithm based on it. The algorithm breaks the threshold of 2 for approximating MULTIWAY C UT. achieving a performance ratio of at most 1.5 - 1/k. This improves the p revious result for every value of k. In particular, for k = 3 we get a rati o of 7/6 < 4/3. (C) 2000 Academic Press.