树上具有惩罚费用的限制性node multicut问题的近似算法  

An Approximate Algorithm for Constrained node multicut Problem on Trees with Penalty Costs

作　　者：杨惠娟 段江梅 杨子兰 YANG Huijuan;DUAN Jiangmei;YANG Zilan(School of Mathematics and Statistics,Zhaotong University,Zhaotong 657000,China;Department of Information,Lijiang Culture and Tourism College,Lijiang 674199,China)

机构地区：[1]昭通学院数学与统计学院,云南昭通657000 [2]丽江文化旅游学校信息学院,云南丽江674199

出　　处：《长春师范大学学报》2024年第2期1-6,共6页Journal of Changchun Normal University

基　　金：云南省教育厅科学研究项目“不同图上限制性斯坦纳多割集问题的复杂性分析及算法设计研究”(2022J0979)。

摘　　要：具有惩罚费用的限制性node multicut问题是在限制性node multicut问题的基础上进一步提出的新问题,该问题在每一个终端点对上都增加了一个惩罚费用,如果终端点对断开就不需要支付惩罚费用,否则就要支付惩罚费用,目标是求断开终端点对所选非终端点的权重之和与未断开的终端点对的惩罚费用之和最小,主要将该问题限制在树上进行研究,针对树上具有惩罚费用的限制性node multicut问题,将该问题转换成树上限制性node multicut问题进行研究,利用线性规划理论设计了求解树上限制性node multicut问题的原始-对偶算法,并将该算法求得的解转化回树上具有惩罚费用的限制性node multicut问题的解,最后证明利用这种方式求得的解的近似值为2.The constrained node multicut problem with penalty costs is a new problem that builds on the restricted node multicut problem by adding a penalty cost to each terminal pair,which is not paid if the terminal pair is disconnected,but is paid otherwise.The goal is to find the minimum sum of the weight of the disconnected terminal endpoint to the selected non-terminal endpoint and the sum of the penalty cost of the undisconnected terminal pair.This problem is mainly restricted to the tree for research,and the restricted node multicut problem with penalty cost on the tree is converted into the restricted node multicut problem on the tree for research.Based on linear programming theory,a primal-dual algorithm is designed to solve the restricted node multicut problem on trees,and the solution obtained by the algorithm is transformed back into the solution of the restricted node multicut problem with penalty cost on trees.Finally,it is proved that the approximate value of the solution obtained by this method is 2.

关 键 词：树 对偶理论 线性规划 原始-对偶算法 

分 类 号：O157.5[理学—数学]