Approximation algorithms for the Bipartite Multicut problem

DOI10.1016/J.IPL.2010.02.002zbMATH Open1209.68644arXivcs/0609031OpenAlexW2062782068MaRDI QIDQ991784FDOQ991784

Authors: Sreyash Kenkre, Sundar Vishwanathan 

Publication date: 7 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: 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 {�f 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 $el{l}_2^2$ Metrics.

Full work available at URL: https://arxiv.org/abs/cs/0609031

Recommendations

• On the hardness of approximating Multicut and Sparsest-Cut
• Hardness of cut problems in directed graphs
• Algorithm Theory - SWAT 2004
• Approximation and Online Algorithms
• Approximation Algorithms for Steiner and Directed Multicuts

zbMATH Keywords

approximation algorithmsBipartite Multicut

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• Geometric algorithms and combinatorial optimization
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Expander flows, geometric embeddings and graph partitioning
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• Title not available (Why is that?)
• Packing directed circuits fractionally

Cited In (3)

• An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees
• Simplex partitioning via exponential clocks and the multiway cut problem
• Some heuristics for the binary paint shop problem and their expected number of colour changes

This page was built for publication: Approximation algorithms for the Bipartite Multicut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991784)