neal young / Karger04Rounding

Mathematics of Operations Research 29(3):04360461(2004); STOC'99The multiwaycut problem is, given a weighted graph and $k > 2$ terminal nodes, to find a minimumweight set of edges whose removal separates all the terminals. The problem is NPhard, and even NPhard to approximate within $1+δ$ for some small $δ > 0$.
This paper gives a 12/11approximation algorithm for $k=3$ and a 1.3438approximation algorithm in general. Working on this result was particularly fun because the problem of designing the algorithm was itself formulated as an optimization problem and approximately solved by computer. These computations guided the final (noncomputational) solutions.
The paper also gives a proof that for a general class of ``geometric embedding'' relaxations, there are always randomized rounding schemes that match the integrality gap. (Another example of such a geometricembedding relaxation is the semidefiniteprogramming relaxation of maxcut by Goemans and Williamson [1995].)
The geometric relaxation is due to Calinescu, Karloff, and Rabani [1998]. After our paper, the approximation ratio for general $k$ was subsequently improved to 1.3238 in [2013].Journal version of [1999].
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.