An improved approximation algorithm for multiway cut
An improved approximation algorithm for multiway cut
复制标题
DOI：
10.1145/276698.276711
复制
发表时间：
1998-05
期刊：
影响因子：
--
通讯作者：
G. Călinescu;H. Karloff;Y. Rabani
中科院分区：
文献类型：
--
作者：
G. Călinescu;H. Karloff;Y. Rabani
给定一个有边代价的无向图和k个节点的子集，称为终端，多路切割是边的子集，其移除将每个终端与其他终端断开。多路切割是寻找成本最小的多路切割的问题。此前，Dahlhaus、Johnson、Papadimitriou、Seymour和Yannakakis提出了一个非常简单的组合算法，给出了2（1?1k）的性能保证。本文提出了一种新的多路切割线性规划松弛算法，并在此基础上提出了一种新的逼近算法。该算法突破了近似多路切割的阈值2，实现了最高1.5?1k的性能比。这改进了前面对每个k值的结果。特别是，对于k=3，我们得到76<43的比率。
Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due to Dahlhaus, Johnson, Papadimitriou, Seymour, and Yannakakis gave a performance guarantee of 2(1?1k). In this paper, we present a new linear programming relaxation for Multiway Cut and a new approximation algorithm based on it. The algorithm breaks the threshold of 2 for approximating Multiway Cut, achieving a performance ratio of at most 1.5?1k. This improves the previous result for every value of k. In particular, for k=3 we get a ratio of 76<43.