Approximation Algorithms for the Bipartite Multi-cut Problem
<|reference_start|>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 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.<|reference_end|>
@article{kenkre2006approximation,
    title={Approximation Algorithms for the Bipartite Multi-cut Problem},
    author={Sreyash Kenkre and Sundar Vishwanathan},
    journal={arXiv preprint arXiv:cs/0609031},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609031},
    primaryClass={cs.CC cs.DS}
}