Record Details

Approximation algorithms for the Bipartite Multicut problem

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Approximation algorithms for the Bipartite Multicut problem
 
Creator KENKRE, S
VISHWANATHAN, S
 
Subject approximation algorithms
bipartite multicut
 
Description 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. .
 
Publisher ELSEVIER SCIENCE BV
 
Date 2011-07-24T10:27:59Z
2011-12-26T12:51:22Z
2011-12-27T05:34:43Z
2011-07-24T10:27:59Z
2011-12-26T12:51:22Z
2011-12-27T05:34:43Z
2010
 
Type Article
 
Identifier INFORMATION PROCESSING LETTERS, 110(8-9), 282-287
0020-0190
http://dx.doi.org/10.1016/j.ipl.2010.02.002
http://dspace.library.iitb.ac.in/xmlui/handle/10054/6395
http://hdl.handle.net/10054/6395
 
Language en