A lower bound of 8/(7+1/k-1) on the integrality ratio of the Calinescu-Karloff-Rabani relaxation for multiway cut
Given an edge-weighted graph and a subset of k vertices called terminals, a multiway cut is a partition of the vertices into k components, each containing exactly one terminal. The multiway cut problem is to find a multiway cut minimizing the sum of the weights of edges with endpoints in different components. Recently, Calinescu et al. described an approximation algorithm based on a geometric embedding of the graph's vertices into R-k. We present a lower bound of 8/(7 + 1/k-1) the integrality ratio of this relaxation. (C) 2000 Elsevier Science B.V. All rights reserved.
lower bounds multiway cuts graph algorithms approximation ratio