@inbook{2c21737a52684eb9af18eceeaa1ff83c,
title = "Approximating Steiner k-cuts",
abstract = "We consider the Steiner k-cut problem, which is a common generalization of the k-cut problem and the multiway cut problem: given an edge-weighted undirected graph G = (V, E), a subset of vertices X ⊆ V called terminals, and an integer k ≤ |X|, the objective is to find a minimum weight set of edges whose removal results in k disconnected components, each of which contains at least one terminal. We give two approximation algorithms for the problem: a 2 - 2/k-approximation based on Gomory-Hu trees, and a 2 - 2/|X|-approximation based on LP rounding. The latter algorithm is based on roundihg a generalization of a linear programming relaxation suggested by Naor and Rabani [8]. The rounding uses the Goemans and Williamson primal-dual algorithm (and analysis) for the Steiner tree problem [4] in an interesting way and differs from the rounding in [8]. We use the insight from the rounding to develop an exact bi-directed formulation for the global minimum cut problem (the k-cut problem with k = 2).",
keywords = "K-Cut, Minimum cut, Multiway Cut, Primal-dual, Steiner tree",
author = "Chandra Chekuri and Sudipto Guha and Joseph Naor",
year = "2003",
doi = "10.1007/3-540-45061-0_17",
language = "English (US)",
isbn = "3540404937",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "189--199",
editor = "Baeten, {Jos C. M.} and Lenstra, {Jan Karel} and Joachim Parrow and Woeginger, {Gerhard J.}",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}