Approximation algorithms for the Bipartite Multicut problem
We introduce the Bipartite Multicut problem. This is a generalization of the st-Mincut problem is similar to the Multicut problem and also turns out to be an immediate generalization of the Min UnCut problem. We prove that this problem is NP-hard and then present an SDP based approximation algorithm. The SDP based approximation algorithm uses the structure theorem of l(2)(2) metrics along with region growing techniques. (C) 2010 Elsevier B.V. All rights reserved.
approximation algorithms bipartite multicut