Computer Science – Data Structures and Algorithms
Scientific paper
2002-05-19
Mathematics of Operations Research 29(3):0436-0461(2004)
Computer Science
Data Structures and Algorithms
Conference version in ACM Symposium on Theory of Computing (1999). To appear in Mathematics of Operations Research
Scientific paper
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. Calinescu, Karloff, and Rabani (1998) gave an algorithm with performance guarantee 3/2-1/k, based on a geometric relaxation of the problem. In this paper, we give improved randomized rounding schemes for their relaxation, yielding a 12/11-approximation algorithm for k=3 and a 1.3438-approximation algorithm in general. Our approach hinges on the observation that the problem of designing a randomized rounding scheme for a geometric relaxation is itself a linear programming problem. The paper explores computational solutions to this problem, and gives a proof that for a general class of geometric relaxations, there are always randomized rounding schemes that match the integrality gap.
Karger David
Klein Phil
Stein Cliff
Thorup Mikkel
Young Neal E.
No associations
LandOfFree
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-11966