Approximation Algorithms For Submodular Hitting Set Problems With Linear/Submodular Penalties

In this paper,we consider three variants of the hitting set problem:the submodular hitting set problem with linear/submodular penalties and the submodular hitting set problem.For the submodular hitting set problem with linear penalties,we give a linear pro-gram.When applying the primal dual technique directly to the dual program for the problem,we cannot control the dual ascending process in polynomial time.To over-come this difficulty,we first weaken the dual program,and then design a primal dual k1-approximation algorithm for the submodular hitting set problem with linear penalties,where k1 is the maximum number of vertices in all hyperedges(the same below).For the submodular hitting set problem with submodular penalties,we also design a primal dual 2k1-approximation algorithm by using the primal dual technique.Then by using the results of S.Iwata and K.Nagano[22]on the submodular set covering problem,we transform the submodular hitting set problem with submodular penalties into the submodular set covering problem,and obtain a k1+1-approximation algorithm,which shows that there exists a better result than the primal dual approximation algorithm.When penalties become infinity,the two problems above end up with the submod-ular hitting set problem.For the submodular hitting set problem,we construct linear programs.By using the Lovasz extension theory of submodular functions,the subbase theory and the primal dual technique,we design a primal dual approximation algorithm,where the approximation ratio does not exceed kr0,where kr0 ? k1.Our result is better than N.Kamiyama's[24]on the problem of minimizing the submodular function under linear covering constraints.