带次模惩罚的部分命中集问题的近似算法  

A Primal-dual Approximation Algorithm for the Partial Hitting Set Problem with Submodular Penalties

作　　者：刘钦 侯波[1] 张更生[1] 刘稳[1] LIU Qin;HOU Bo;ZHANG Gengsheng;LIU Wen(College of Mathematical Sciences,Hebei Normal University,Hebei,Hebei Shijiazhuang 050024,China)

机构地区：[1]河北师范大学数学科学学院,河北石家庄050024

出　　处：《河北师范大学学报（自然科学版）》2024年第5期448-455,共8页Journal of Hebei Normal University：Natural Science

基　　金：河北省自然科学基金(A2022205024,A2023205009);河北师范大学交叉学科研究基金(L2024J01);河北师范大学研究生创新资助项目(YCXZZSS202402)。

摘　　要：研究了带次模惩罚的部分命中集问题.给定一个超图H=(V,E),一个定义在V上的费用函数,一个定义在2~E上的次模惩罚函数,和一个非负整数k.问题的目标是找一个顶点子集S?V,使得S至少覆盖k条超边,且S的总费用加上未被S覆盖的超边集的惩罚费用之和最小.设计了一个基于原始-对偶的两阶段组合算法来解决该问题.当次模惩罚函数是正规化的且非减时,得到算法的近似因子为l+1,其中l是超边所含的顶点数的最大值.We consider the partial hitting set problem with submodular penalties.In this problem,we are given a hypergraph H=(V,E),a cost function defined on V,a submodular penalty function defined on2~Eand a nonnegative integer k.The goal is to find a vertex subset S?V such that S covers at least k hyperedges and the total cost of the vertices in Splus the penalty of the hyperedges uncovered is minimized.We design a primal-dual approximation algorithm for this problem and prove that the algorithm has an approximation factor of l+1,where l is the maximum size of hyperedges.

关 键 词：近似算法 命中集问题 次模惩罚 原始-对偶 

分 类 号：O175.2[理学—数学]