View article

Given an undirected graph with edge costs and a subset of k 2 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to find a minimum-cost multiway cut. This problem is Max-SNP hard. Recently Calinescu, Karloff, end Rabbi (STOC’98) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (312-l/k)-approximation algorithm.

In this paper. we study their geometric relaxation. In particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). For k= 3, we show the integrality gap is 12/11. giving tight upper and lower bounds. That is, we exhibit a graph with integrality gap 12/11 and give an algorithm that finds a cut of value 12/11 times the relaxation value. This is the best possible …