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 contai ning exactly one terminal. The multiway cut problem is to find a multiway c ut minimizing the sum of the weights of edges with endpoints in different c omponents. 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.