A Bicriteria Approzimation Algorithm for Generalized K-Multicut in Trees

摘要：

Given a tree T = (V, E) with costs defined on edges, a positive integer k, and l terminal sets S1, S2,...., Sl with every Si (∈) V, the generalized k-Multicut in trees problem (k-GMC(T)) asks to find an edge subset in E at the minimum cost such that its removal cuts at least k terminal sets. The k-GMC(T) problem is a natural generalization of the classical Multicut in trees problem and the Multiway Cut in trees problem. This problem is hard to be approximated within O(n1/6-∈) for some small constant ∈ > 0 (Zhang, CiE07). Based on a greedy approach and a rounding technique in linear programming, we give a bicriteria approximation algorithm for k-GMC(T). Our algorithm outputs in polynomial time a solution which cuts at least (1 - ∈)k terminal sets and whose cost is within 2/∈·l times of the optimum for any small constant ∈ > 0, and hence gives sublinear approximation ratio for k-GMC(T).

作者: Peng Zhang Darning Zhu Junfeng Luan

作者单位: School of Computer Science and Technology Shandong University Jinan 250101, P.R.China

会议类型: 国际会议

会议名称: The Second International Joint Conference on Computational Science and Optimization(CSO 2009)(2009 国际计算科学与优化会议)

会议地点: 三亚

会议语种:英文

页码: 1749-1752

在线出版日期: 2009-04-24（万方平台首次上网日期，不代表论文的发表时间）