树上推广的Multicut问题的近似算法  

Approximation Algorithms for Generalized Multicut in Trees

作　　者：张鹏[1] 

机构地区：[1]山东大学计算机科学与技术学院,济南250101

出　　处：《计算机研究与发展》2008年第7期1195-1202,共8页Journal of Computer Research and Development

基　　金：国家杰出青年基金项目(60325206);国家自然科学基金项目(60310213)

摘　　要：给定边上有费用的树T,终端集合族X={S1,S2,…,Sl},推广的Multicut问题询问费用最小的边集,使得在树上删除边集中的边能够断开每一个终端集.推广的Multicut问题有其独立的研究意义,因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的Steiner Forest问题的对偶问题.树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题近似求解.对于该问题的Prize-collecting版本,给出了原始-对偶的3倍近似算法.对于该问题的k版本,通过非一致的途径给出了近似比为min{2(l-k+1),k}的近似算法.以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似到O(n1/6-ε)以内是困难的(对某个小的常数ε>0).Given a tree T with costs on edges and a collection of terminal sets X={S1,S2,…,Sl},the generalized multicut in trees problem asks to find a set of edges on T whose removal cuts every terminal set in X,such that the total cost of the picked edges is minimized.The problem has its own interest since it naturally generalizes the classical multicut problem and the multiway cut problem,respectively,and also is the dual of the generalized Steiner forest problem.It is shown that the full version of the problem can be approximated within a factor of 2 by reducing it to the classical multicut in trees problem.In the prize-collecting version of the problem,a terminal set must pay the penalty πi if it is not cut by the picked edges.A primal-dual 3-approximation algorithm is given for the prize-collecting generalized multicut in trees problem via primal-dual schema.The k-version of the problem has to cut at least k terminal sets at the minimum cost,where k is a given parameter.It is shown that the k-version of the problem can be approximated within a factor of min{2（l-k＋1）,k} via a non-uniform approach.Furthermore,it is shown that there is an interesting relation between the generalized k-multicut in trees problem and the dense k-subgraph problem,implying that approximating the k-version of the problem within O（n1 6-ε） for some small ε〉0 is difficult.

关 键 词：Multicut 树 线性规划 近似算法 组合优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]