带线性惩罚的次模边点控制集问题的近似算法

An Approximation Algorithm for the Submodular Edge Vertex Domination Set Problem with Linear Penalties

考虑带线性惩罚的次模边点控制集问题,给定一个无向图G=(V,E),且V中每个顶点都有一个非负惩罚,E的每个边子集都有一个非负权值.称e={u,v}∈E为边点控制顶点w,如果w∈N[u]∪N[v],这里N[u],N[v]分别为顶点u,v的闭邻域.带线性惩罚的次模边点控制集问题的目标是寻找一个边子集D,使得D的权值与未被D边点控制的顶点的惩罚费用之和最小.利用原始对偶技巧给出此问题的一个k-近似算法,其中k=maxv∈V|N[v]|.

In this paper, we consider the submodular edge vertex domination set problem with linear penalties.In this problem, we are given an undirected graph G=(V,E) with a nonnegative penalty for each vertex and a nonnegative cost for each edge subset.An edge e={u,v}in E is called to edge vertex dominate a vertex w,whenever w is in N[u]∪N[v],where N[u],N[v] are the closed neighborhoods of u,v respectively.The goal of the submodular edge vertex domination set problem with linear penalties is to find an edge subset D such that the sum of the cost of D and the penalties of the undominated vertices by D is minimized.In this paper, we mainly use the primal dual technique to get a k-approximation algorithm for the submodular edge vertex domination set problem with linear penalties, where k=maxv∈V|N[v]|.