Improved results for directed multicut
Improved results for directed multicut
复制标题
DOI：
--
复制
发表时间：
2003-01
期刊：
影响因子：
--
通讯作者：
Anupam Gupta
中科院分区：
文献类型：
--
作者：
Anupam Gupta
我们给出了最小有向多割问题的简单算法，并表明它给出了 O(√n) 近似值。这改进了 Cheriyan、Karloff 和 Rabani [1] 之前通过更复杂的算法获得的 O(√n log k) 的近似保证。
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.