file.pdf (61.66 kB)

Improved Results for Directed Multicut

Download (61.66 kB)
journal contribution
posted on 01.06.2004, 00:00 by Anupam Gupta
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.

History

Date

01/06/2004

Usage metrics

Exports