Approximation Algorithms for the Bipartite Multi-cut Problem

Details Approximation Algorithms for the Bipartite Multi-cut Problem Approximation Algorithms for the Bipartite Multi-cut Problem

2006-09-07

arxiv.org/abs/cs/0609031v2

Computer Science

Computational Complexity

11 pages

Scientific paper

We introduce the {\it Bipartite Multi-cut} problem. This is a generalization of the {\it st-Min-cut} problem, is similar to the {\it Multi-cut} problem (except for more stringent requirements) and also turns out to be an immediate generalization of the {\it Min UnCut} problem. We prove that this problem is {\bf NP}-hard and then present LP and SDP based approximation algorithms. While the LP algorithm is based on the Garg-Vazirani-Yannakakis algorithm for {\it Multi-cut}, the SDP algorithm uses the {\it Structure Theorem} of $\ell_2^2$ Metrics.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for the Bipartite Multi-cut Problem 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 Approximation Algorithms for the Bipartite Multi-cut Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for the Bipartite Multi-cut Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-317759