Improved results for directed multicut

Anupam Gupta

Abstract

We give a simple algorithm for the Minimum Directed Multicut problem, and show that it gives an O(√n)-approximation. This improves on the previous approximation guarantee of O(√n log k) of Cheriyan, Karloff and Rabani [1], which was obtained by a more sophisticated algorithm.
BibTeX
@inproceedings{gupta2003improved,
  author = {Anupam Gupta},
  title = {{Improved results for directed multicut}},
  booktitle = {SODA},
  year = {2003},
}

Loading related content...

Figure