Rounding algorithms for a geometric embedding of minimum multiway cut.

*(English)*Zbl 1082.90149Summary: Given an undirected graph with edge costs and a subset of \(k\geq 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, G. Calinescu, H. Karloff and Y. Rabani [J. Comput. System Sci. 60, 564–574 (2000; Zbl 0986.90043)] gave a novel geometric relaxation of the problem and a rounding scheme that produced a \((3/2-1/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 family of graphs with integrality gaps arbitrarily close to \(12/11\) and give an algorithm that finds a cut of value \(12/11\) times the relaxation value. Our lower bound shows that this is the best possible performance guarantee for any algorithm based purely on the value of the relaxation. Our upper bound meets the lower bound and improves the factor of \(7/6\) shown by Calinescu et al.

For all \(k\), we show that there exists a rounding scheme with performance ratio equal to the integrality gap, and we give explicit constructions of polynomial-time rounding schemes that lead to improved upper bounds. For \(k=4\) and \(5\), our best upper bounds are based on computer-constructed rounding schemes (with computer proofs of correctness). For general \(k\) we give an algorithm with performance ratio \(1.3438 - \epsilon_k\).

Our results were discovered with the help of computational experiments that we also describe here.

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 family of graphs with integrality gaps arbitrarily close to \(12/11\) and give an algorithm that finds a cut of value \(12/11\) times the relaxation value. Our lower bound shows that this is the best possible performance guarantee for any algorithm based purely on the value of the relaxation. Our upper bound meets the lower bound and improves the factor of \(7/6\) shown by Calinescu et al.

For all \(k\), we show that there exists a rounding scheme with performance ratio equal to the integrality gap, and we give explicit constructions of polynomial-time rounding schemes that lead to improved upper bounds. For \(k=4\) and \(5\), our best upper bounds are based on computer-constructed rounding schemes (with computer proofs of correctness). For general \(k\) we give an algorithm with performance ratio \(1.3438 - \epsilon_k\).

Our results were discovered with the help of computational experiments that we also describe here.