Improved results for directed multicut
Lists
Only you see this
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...