具有次模惩罚的k-集奖最小顶点覆盖问题(k-PCVCS)是最小顶点覆盖问题的推广，是图论和组合优化中最重要和最基本的问题之一。
这个问题是选择一个至少覆盖k条边的顶点集，目标是最小化所选集合中顶点的总代价加上未覆盖边集的惩罚，其中惩罚由子模函数决定。
为了解决k-PCVCS, Xiaofei Liu等人在《计算机科学前沿》(Frontiers of Computer Science)上发表了他们的新研究。
在研究中，他们首先证明了算法1可以在0 (n16r+n17)中实现，其中r是一个函数求值的时间。然后，他们证明了算法2是k-PCVCS的3逼近算法。具体来说，如果惩罚函数是线性的，则算法2是一个2逼近算法。
未来的工作可能集中在研究具有一般惩罚的版本，如次加性或超模惩罚。同时，具有硬容量的k-PCVCS值得探索，其中每个顶点v最多有Cv条边被覆盖。
更多信息:刘晓飞等人，一种具有次模惩罚的k奖收集最小顶点覆盖问题的原对偶逼近算法，计算机科学前沿(2022)。引文:用于k-prize-collecting minimum vertex cover problem with submodular penalties (2023, August 23)的原始对偶近似算法(2023年8月27日检索自https://techxplore.com/news/2023-08-primal-dual-approximation-algorithm-k-prize-collecting-minimum.html)。除为私人学习或研究目的而进行的任何公平交易外，未经书面许可，不得转载任何部分。内容仅供参考之用。
