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.
| Original language | English (US) |
|---|---|
| Pages | 454-455 |
| Number of pages | 2 |
| State | Published - 2003 |
| Event | Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: Nov 2 1998 → Nov 3 1998 |
Other
| Other | Configuralble Computing: Technology and Applications |
|---|---|
| Country/Territory | United States |
| City | Boston, MA |
| Period | 11/2/98 → 11/3/98 |
ASJC Scopus subject areas
- Software
- General Mathematics