neal young / Karger04Rounding
-
Mathematics of Operations Research 29(3):0436-0461(2004); STOC'99
The multiway-cut problem is, given a weighted graph and \(k > 2\)
terminal nodes, to find a minimum-weight set of edges whose
removal separates all the terminals. The problem is NP-hard,
and even NP-hard to approximate within \(1+\delta\) for some small
\(\delta > 0\).
This paper gives a 12/11-approximation algorithm for \(k=3\) and a 1.3438-approximation 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 (non-computational) 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 geometric-embedding relaxation is the semidefinite-programming relaxation of max-cut 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.