Approximation Algorithms For Submodular Edge Cover Problems With Linear/Submodular Penalties

In this paper,we study approximation algorithms of the submodular edge cover problem with linear penalties and the submodular edge cover problem with submodular penalties.For the submodular edge cover problem with linear penalties,we first give its linear program and the corresponding dual program.By using the weaker form of dual program we design an approximation algorithm for this problem and analyze its performance,yielding an approximation ratio ?,where ? is the maximum degree of the graph.For the submodular edge cover problem with submodular penalties,we first give its linear program,then we give its its dual program and a weaker form of the dual program.Further we design an approximation algorithm with the approximation ratio 2?.In addition,we transform this problem into a submodular set cover problem,and by using the result of the submodular set cover problem show that there exists an algorithm with the approximation ratio ? + 1,where ? is the maximum degree of the graph.