Approximation Algorithms for the Bipartite Multi-cut Problem

Simple item page
dc.creatorKenkre, Sreyash
dc.creatorVishwanathan, Sundar
dc.date2006-09-07
dc.date2006-09-26
dc.date.accessioned2026-07-07T07:23:48Z
dc.date.available2026-07-07T07:23:48Z
dc.descriptionWe 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.
dc.description11 pages
dc.identifierhttps://arxiv.org/abs/cs/0609031
dc.identifierhttp://arxiv.org/abs/cs/0609031
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/116118
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.titleApproximation Algorithms for the Bipartite Multi-cut Problem
dc.typetext

Files

Collections

arXiv