Approximation algorithms for the submodular edge cover problem with submodular penalties

Abstract In this paper, we consider the submodular edge cover problem with submodular penalties. In this problem, we are given an undirected graph G = ( V , E ) with vertex set V and edge set E. Assume the covering cost function c : 2 E → R + and the penalty function p : 2 V → R + are both submodular with p non-decreasing, c ( ∅ ) = 0 and p ( ∅ ) = 0 . The goal of the submodular edge cover problem with submodular penalties is to select an edge subset to cover some vertices and penalize the vertex subset containing uncovered vertices such that the total cost of covering and penalty is minimized. For this problem, we first give a 2Δ-approximation algorithm by using a primal-dual technique, where Δ is the maximal degree of the graph G. Then we transform this problem into a submodular set cover problem, and by applying a known result for the submodular set cover problem we conclude that there is an approximation algorithm with an approximation ratio Δ + 1 .