1. 引言
目前关于组合优化问题的奖励收集形式或部分形式的研究已有许多好的结果,比如k-中心问题 [1]。k-最小生成树问题 [2],k-Steiner树问题 [3],k-奖励收集Steiner树问题 [4] 和部分覆盖问题 [5]。本篇文章主要研究树上k-奖励收集多割问题(k-PCMT)的近似算法。k-PCMT问题实例是指给定一个无向树
,对于每条边
都有一个非负费用
,令
是一个由m个结点对构成的集合,且对于每一个点对
都有一个非负惩罚费用
,并给定一个参数
。设
是边集的一个子集,对某个
,
称为被M分割,如果
不在T\M的同一个连通分支中。k-PCMT问题是找到一个边子集M,使得M至少分割k个结点对,且使得M中的边费用与未被分割的顶点对的惩罚费用之和最小。
k-PCMT问题是组合优化著名的NP难问题——树上多割问题的变形,是树上奖励收集的多割问题和树上部分割问题的一个推广。对于树上的多割问题,Garg等人在文献 [5] 中提出了近似比为2的原始对偶算法。
树上奖励收集的多割(PCMT)问题实例是给定一个无向树
,一个由m个顶点对构成的集合
。E中的每个边都有一个非负费用值
,P中的每个顶点对
都有一个非负惩罚费用
。PCMT问题是找到一个边集
,使得M中的边费用加上未被分割的顶点对的惩罚费用最小。对于树上奖励收集的多割问题,Levin和Segev在 [6] 中通过修改原始树和结点对的集合方法将其转化为树上的多割问题,并给出了该问题的一个近似比为2的近似算法。本文称此算法为算法1。
树上部分多割(PMT)问题实例是给定一个无向树
,一个由m个顶点对构成的集合
。E中的每个边都有一个非负费用值
,给定一个参数
。PMT问题是找到一个边集
,使得M至少分割k个顶点对,并且使M中的边费用之和最小。Levin和Segev在 [6] 中利用拉格朗日松弛技巧提出了关于求解树上部分割问题的一个近似比为
的近似算法,其中
是一个任意固定的正数。本文称此算法为算法2。
本文利用上述两个算法给出求解k-PCMT问题的一个近似比为
的近似算法。
2. 算法和近似比分析
在本节,我们给出求解k-PCMT问题的一个近似算法。令OPT表示k-PCMT问题的最优解的目标函数值。令
为一个确定的参量。并且假设每条边的费用至多等于
乘以OPT。注意Levin和Segev就是在此假设下研究了树上部分多割问题(见文献 [6] )。本文也在此假设下研究k-PCMT问题。
算法
输入:无向树
,对每一条边,边费用
,对每个顶点对
,惩罚费用
,正整数
。
输出:边子集M,未被M分割的顶点对的集合R。
步骤1:对一个PCMT实例
,应用PCMT问题的算法1。令
是该算法的输出解。若此时
中的边已经分割至少k个顶点对,则输出
作为k-PCMT问题实例的一个可行解,算法停止;否则进行步骤2。
步骤2:规定步骤1中选中的边重新赋值为0,其余边的权值不变,得到新的边费用函数
。令
步骤1中分割的顶点对个数。对一个PMT实例
,应用PMT算法2。令
是该算法的输出解。输出
作为k-PCMT问题实例的一个可行解,算法停止。
下面我们分析一下这个算法的近似比。
引理1:设
是PMT问题的最优解,则有
证明:因为费用函数和惩罚函数都是非负的,则有
因为k-PCMT的最优解是PMT的可行解,所以最后一个不等式成立。证毕。
因为k-PCMT问题的任一个可行解都是PCMT问题的可行解,所以有以下引理。
引理2:PCMT问题的最优解
满足
引理3:若算法在步骤1就停止,则此时输出的解
满足
证明:由算法可知,输出解
是由步骤1得到的,则
一定分割至少k个顶点对,故是k-PCMT问题的可行解。假设
是PCMT问题的最优值,那么由引理2我们可以得到
引理4:若算法在第二步时停止,则此时
满足
证明:显然有
成立。由于
分割了至少k个顶点对,所以
是k-PCMT问题的可行解。因为费用函数c和
都是非负的且
,所以有
由引理1和引理2可知
综上我们有下面主要结论。
定理4:存在一个k-PCMT问题的近似比为
的近似算法。
3. 结论
本文中,笔者采用PCMT问题和PMT问题的两个算法作为子算法给出了求解k-PCMT问题的一个新算法。
基金项目
河北省自然科学基金(A2019205089);河北师范大学研究生创新资助项目(CXZZSS2021045)。