河北师范大学，河北 石家庄

收稿日期：2021年7月4日；录用日期：2021年7月23日；发布日期：2021年8月6日

摘要

在树上k-奖励收集多割问题中，给定一个无向树 $T=\left(V,E\right)$，一个由m个结点对构成的集合 $P=\left\{\left(s_1,t_1\right),\left(s_2,t_2\right),\cdots ,\left(s_m,t_m\right)\right\}$ 和一个参数k且 $k\le m$。E中的每一条边都有一个非负成本 $c_e$，P中的每一个结点对都有一个非负惩罚成本 ${\pi }_i$。目标是求一个能分离P中至少k个结点对的多割M，使得多割M中边的成本与未被M分割的结点对的惩罚成本之和最小。这个问题是著名的树上的多割问题的推广。在本文中，我们设计了一个树上k-奖励收集多割问题的近似比为 $\left(\frac{14}{3}+\epsilon \right)$ 的近似算法，其中 $\epsilon$ 是任意一个确定的正数。

关键词

多割，k-奖励收集多割，近似算法

An Approximation Algorithm for the k-Prize-Collecting Multicut on a Tree Problem

Chenfei Hou

Hebei Normal University, Shijiazhuang Hebei

Received: Jul. 4^th, 2021; accepted: Jul. 23^rd, 2021; published: Aug. 6^th, 2021

ABSTRACT

In the k-prize-collecting multicut on a tree (k-PCM(T)) problem, we give an undirected tree $T=\left(V,E\right)$, a set of m distinct pairs of vertices $P=\left\{\left(s_1,t_1\right),\left(s_2,t_2\right),\cdots ,\left(s_m,t_m\right)\right\}$ and a parameter k with $k\le m$. Every edge in E has a nonnegative cost $c_e$. Every pair $\left(s_i,t_i\right)$ in P has a nonnegative penalty cost ${\pi }_i$. Our goal is to find a multicut M that separates at least k pairs in P such that the total cost, including the edge cost of the multicut M and the penalty cost of the pairs not separated by M, is minimized. This problem generalizes the well-known multicut on a tree problem. In this paper, we design an approximation algorithm for the k-PCM(T) problem with approximation ratio $\left(\frac{14}{3}+\epsilon \right)$, where $\epsilon$ is a fixed number.

Keywords:Multicut, k-Prize-Collecting Multicut, Approximation Algorithm

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

目前关于组合优化问题的奖励收集形式或部分形式的研究已有许多好的结果，比如k-中心问题 [1]。k-最小生成树问题 [2]，k-Steiner树问题 [3]，k-奖励收集Steiner树问题 [4] 和部分覆盖问题 [5]。本篇文章主要研究树上k-奖励收集多割问题(k-PCMT)的近似算法。k-PCMT问题实例是指给定一个无向树 $T=\left(V,E\right)$，对于每条边 $e\in E$ 都有一个非负费用 $c_e$，令 $P=\left\{\left(s_1,t_1\right),\left(s_2,t_2\right),\cdots ,\left(s_m,t_m\right)\right\}$ 是一个由m个结点对构成的集合，且对于每一个点对 $\left(s_i,t_i\right)$ 都有一个非负惩罚费用 ${\pi }_i$，并给定一个参数 $k\le m$。设 $M\subseteq E$ 是边集的一个子集，对某个 $1\le i\le m$，$\left(s_i,t_i\right)$ 称为被M分割，如果 $s_i,t_i$ 不在T\M的同一个连通分支中。k-PCMT问题是找到一个边子集M，使得M至少分割k个结点对，且使得M中的边费用与未被分割的顶点对的惩罚费用之和最小。

k-PCMT问题是组合优化著名的NP难问题——树上多割问题的变形，是树上奖励收集的多割问题和树上部分割问题的一个推广。对于树上的多割问题，Garg等人在文献 [5] 中提出了近似比为2的原始对偶算法。

树上奖励收集的多割(PCMT)问题实例是给定一个无向树 $T=\left(V,E\right)$，一个由m个顶点对构成的集合 $P=\left\{\left(s_1,t_1\right),\left(s_2,t_2\right),\cdots ,\left(s_m,t_m\right)\right\}$。E中的每个边都有一个非负费用值 $c_e$，P中的每个顶点对 $\left(s_i,t_i\right)$ 都有一个非负惩罚费用 ${\pi }_i$。PCMT问题是找到一个边集 $M\subseteq E$，使得M中的边费用加上未被分割的顶点对的惩罚费用最小。对于树上奖励收集的多割问题，Levin和Segev在 [6] 中通过修改原始树和结点对的集合方法将其转化为树上的多割问题，并给出了该问题的一个近似比为2的近似算法。本文称此算法为算法1。

树上部分多割(PMT)问题实例是给定一个无向树 $T=\left(V,E\right)$，一个由m个顶点对构成的集合 $P=\left\{\left(s_1,t_1\right),\left(s_2,t_2\right),\cdots ,\left(s_m,t_m\right)\right\}$。E中的每个边都有一个非负费用值 $c_e$，给定一个参数 $k\le m$。PMT问题是找到一个边集 $M\subseteq E$，使得M至少分割k个顶点对，并且使M中的边费用之和最小。Levin和Segev在 [6] 中利用拉格朗日松弛技巧提出了关于求解树上部分割问题的一个近似比为 $\left(\frac{8}{3}+\epsilon \right)$ 的近似算法，其中 $\epsilon$ 是一个任意固定的正数。本文称此算法为算法2。

本文利用上述两个算法给出求解k-PCMT问题的一个近似比为 $\left(\frac{14}{3}+\epsilon \right)$ 的近似算法。

2. 算法和近似比分析

在本节，我们给出求解k-PCMT问题的一个近似算法。令OPT表示k-PCMT问题的最优解的目标函数值。令 $\epsilon >0$ 为一个确定的参量。并且假设每条边的费用至多等于 $\epsilon$ 乘以OPT。注意Levin和Segev就是在此假设下研究了树上部分多割问题(见文献 [6] )。本文也在此假设下研究k-PCMT问题。

算法

输入：无向树 $T=\left(V,E\right)$，对每一条边，边费用 $c_e\ge 0$，对每个顶点对 $\left(s_i,t_i\right)$，惩罚费用 ${\pi }_i\ge 0$，正整数 $k\le m$。

输出：边子集M，未被M分割的顶点对的集合R。

步骤1：对一个PCMT实例 $\left(T,c,\pi \right)$，应用PCMT问题的算法1。令 $F_{PCMT}=\left(M_{PCMT},P_{PCMT}\right)$ 是该算法的输出解。若此时 $M_{PCMT}$ 中的边已经分割至少k个顶点对，则输出 $M_{PCMT}$ 作为k-PCMT问题实例的一个可行解，算法停止；否则进行步骤2。

步骤2：规定步骤1中选中的边重新赋值为0，其余边的权值不变，得到新的边费用函数 $c^{\prime }$。令 $k^{\prime }=k-$ 步骤1中分割的顶点对个数。对一个PMT实例 $\left(T,c^{\prime },k^{\prime }\right)$，应用PMT算法2。令 $F_{PMT}=\left(M_{PMT},P_{PMT}\right)$ 是该算法的输出解。输出 $M_{PCMT}\cup M_{PMT}$ 作为k-PCMT问题实例的一个可行解，算法停止。

下面我们分析一下这个算法的近似比。

引理1：设 $\left(M^{*},P^{*}\right)$ 是PMT问题的最优解，则有

${\displaystyle \underset{e\in M_{PMT}^{\ast }}{\sum }{c}_e}\le OPT.$

证明：因为费用函数和惩罚函数都是非负的，则有

$\begin{array}{c}OPT=\underset{e\in M_{k\text{-}PCMT}^{*}}{{\displaystyle \sum }}{c}_e+\underset{\left(s_i,t_i\right)\in P_{k\text{-}PCMT}^{*}}{{\displaystyle \sum }}{\pi }_i\\ \ge \underset{e\in M_{k\text{-}PCMT}^{*}}{{\displaystyle \sum }}{c}_e\\ \ge \underset{e\in M_{PMT}^{*}}{{\displaystyle \sum }}{c}_e.\end{array}$

因为k-PCMT的最优解是PMT的可行解，所以最后一个不等式成立。证毕。

因为k-PCMT问题的任一个可行解都是PCMT问题的可行解，所以有以下引理。

引理2：PCMT问题的最优解 $\left(M_{PCMT}^{*},P_{PCMT}^{*}\right)$ 满足

$\underset{e\in M_{PCMT}^{*}}{{\displaystyle \sum }}{c}_e+\underset{\left(s_i,t_i\right)\in P_{PCMT}^{*}}{{\displaystyle \sum }}{\pi }_i\le OPT.$

引理3：若算法在步骤1就停止，则此时输出的解 $F_{OUT}=\left(M_{OUT},P_{OUT}\right)$ 满足

$\underset{e\in M_{OUT}}{{\displaystyle \sum }}{c}_e+\underset{\left(s_i,t_i\right)\in P_{OUT}}{{\displaystyle \sum }}{\pi }_i\le 2OPT.$

证明：由算法可知，输出解 $F_{OUT}$ 是由步骤1得到的，则 $F_{OUT}$ 一定分割至少k个顶点对，故是k-PCMT问题的可行解。假设 $OP{T}_{PCMT}$ 是PCMT问题的最优值，那么由引理2我们可以得到

$\underset{e\in M_{OUT}}{{\displaystyle \sum }}{c}_e+\underset{\left(s_i,t_i\right)\in P_{OUT}}{{\displaystyle \sum }}{\pi }_i\le 2OP{T}_{PCMT}\le 2OPT.$

引理4：若算法在第二步时停止，则此时 $F_{OUT}=\left(M_{OUT},P_{OUT}\right)$ 满足

$\underset{e\in M_{OUT}}{{\displaystyle \sum }}{c}_e+\underset{\left(s_i,t_i\right)\in P_{OUT}}{{\displaystyle \sum }}{\pi }_i\le \left(\frac{14}{3}+\epsilon \right)OPT.$

证明：显然有 $M_{OUT}=M_{PCMT}\cup M_{PMT}$ 成立。由于 $F_{OUT}$ 分割了至少k个顶点对，所以 $F_{OUT}$ 是k-PCMT问题的可行解。因为费用函数c和 $\pi$ 都是非负的且 $P_{OUT}\subseteq P_{PCMT}$，所以有

$\underset{e\in M_{OUT}}{{\displaystyle \sum }}{c}_e+\underset{\left(s_i,t_i\right)\in P_{OUT}}{{\displaystyle \sum }}{\pi }_i\le \underset{e\in M_{PMT}}{{\displaystyle \sum }}{c}_e+\underset{e\in M_{PCMT}}{{\displaystyle \sum }}{c}_e+\underset{\left(s_i,t_i\right)\in P_{PCMT}}{{\displaystyle \sum }}{\pi }_i.$

由引理1和引理2可知

$\begin{array}{c}\underset{e\in M_{PMT}}{{\displaystyle \sum }}{c}_e+\underset{e\in M_{PCMT}}{{\displaystyle \sum }}{c}_e+\underset{\left(s_i,t_i\right)\in P_{PCMT}}{{\displaystyle \sum }}{\pi }_i\le \left(\frac{8}{3}+\epsilon \right)OP{T}_{PMT}+2OP{T}_{PCMT}\\ \le \left(\frac{8}{3}+\epsilon \right)OPT+2OPT\\ =\left(\frac{14}{3}+\epsilon \right)OPT.\end{array}$

综上我们有下面主要结论。

定理4：存在一个k-PCMT问题的近似比为 $\left(\frac{14}{3}+\epsilon \right)$ 的近似算法。

3. 结论

本文中，笔者采用PCMT问题和PMT问题的两个算法作为子算法给出了求解k-PCMT问题的一个新算法。

基金项目

河北省自然科学基金(A2019205089)；河北师范大学研究生创新资助项目(CXZZSS2021045)。

文章引用

侯晨菲. 树上k-奖励收集多割问题的近似算法
An Approximation Algorithm for the k-Prize-Collecting Multicut on a Tree Problem[J]. 应用数学进展, 2021, 10(08): 2701-2704. https://doi.org/10.12677/AAM.2021.108280

参考文献