| 树上具有惩罚费用的限制性node multicut问题的近似算法 |
| |
| 引用本文： | 杨惠娟,段江梅,杨子兰.树上具有惩罚费用的限制性node multicut问题的近似算法[J].长春师范大学学报,2024(2):1-6. |
| |
| 作者姓名： | 杨惠娟 段江梅 杨子兰 |
| |
| 作者单位： | 1. 昭通学院数学与统计学院 |
| |
| 基金项目： | 云南省教育厅科学研究项目“不同图上限制性斯坦纳多割集问题的复杂性分析及算法设计研究”(2022J0979)； |
| |
| 摘 要： | 具有惩罚费用的限制性node multicut问题是在限制性node multicut问题的基础上进一步提出的新问题，该问题在每一个终端点对上都增加了一个惩罚费用，如果终端点对断开就不需要支付惩罚费用，否则就要支付惩罚费用，目标是求断开终端点对所选非终端点的权重之和与未断开的终端点对的惩罚费用之和最小，主要将该问题限制在树上进行研究，针对树上具有惩罚费用的限制性node multicut问题，将该问题转换成树上限制性node multicut问题进行研究，利用线性规划理论设计了求解树上限制性node multicut问题的原始-对偶算法，并将该算法求得的解转化回树上具有惩罚费用的限制性node multicut问题的解，最后证明利用这种方式求得的解的近似值为2.
|
| 关 键 词： | 树 对偶理论 线性规划 原始-对偶算法 |
|
|
