A 2-approximation algorithm for the directed multiway cut problem

被引：18

作者：

Naor, JS ^{[1
]}

Zosin, L ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 1997年

关键词：

D O I：

10.1109/SFCS.1997.646144

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A directed multiway cut separates a set of terminals s(1),..., s(k) in a directed capacitated graph G = (V, E). Finding a minimum capacity directed multiway cut is an NP-complete problem. We gave a polynomial-time algorithm that achieves an approximation factor of 2 for this problem. This improves the result of Garg, Vazirani and Yannakakis [GVY94] who gave an algorithm that achieves an approximation factor of 2 log k. Our approximation algorithm uses a novel technique for relating a multiway flour function in order to find a directed multiway cut. It also implies that the integrality gap of the linear program for the directed multiway cut problem is at moat 2.

引用

页码：548 / 553

页数：6