Improved results for directed multicut

Anupam Gupta

Research output: Contribution to conferencePaperpeer-review


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.

Original languageEnglish (US)
Number of pages2
StatePublished - 2003
EventConfiguralble Computing: Technology and Applications - Boston, MA, United States
Duration: Nov 2 1998Nov 3 1998


OtherConfiguralble Computing: Technology and Applications
Country/TerritoryUnited States
CityBoston, MA

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Improved results for directed multicut'. Together they form a unique fingerprint.

Cite this