树上具有惩罚费用的限制性node multicut问题的近似算法
An Approximate Algorithm for Constrained node multicut Problem on Trees with Penalty Costs
杨惠娟 1段江梅 1杨子兰2
作者信息
- 1. 昭通学院数学与统计学院,云南 昭通 657000
- 2. 丽江文化旅游学校信息学院,云南 丽江 674199
- 折叠
摘要
具有惩罚费用的限制性node multicut问题是在限制性node multicut 问题的基础上进一步提出的新问题,该问题在每一个终端点对上都增加了一个惩罚费用,如果终端点对断开就不需要支付惩罚费用,否则就要支付惩罚费用,目标是求断开终端点对所选非终端点的权重之和与未断开的终端点对的惩罚费用之和最小,主要将该问题限制在树上进行研究,针对树上具有惩罚费用的限制性node multicut问题,将该问题转换成树上限制性node multicut 问题进行研究,利用线性规划理论设计了求解树上限制性node multicut 问题的原始-对偶算法,并将该算法求得的解转化回树上具有惩罚费用的限制性node multicut问题的解,最后证明利用这种方式求得的解的近似值为 2.
Abstract
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 pen-alty 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 pro-gramming 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.
关键词
树/对偶理论/线性规划/原始-对偶算法Key words
tree/duality theory/linear programming/primordial-duality algorithm引用本文复制引用
基金项目
云南省教育厅科学研究项目(2022J0979)
出版年
2024
NETL
NSTL
万方数据