Approximation Algorithms for the Bipartite Multi-cut Problem

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 pro...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2006-09
Main Authors: Kenkre, Sreyash, Vishwanathan, Sundar
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Mathematical analysis
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422