Submodular Function Minimization under Covering Constraints

This paper addresses the problems of minimizing nonnegative submodular functions under covering constraints, which generalize the vertex cover, edge cover, and set cover problems. We give approximation algorithms for these problems exploiting the discrete convexity of submodular functions. We first present a rounding 2-approximation algorithm for the submodular vertex cover problem based on the half-integrality of the continuous relaxation problem, and show that the rounding algorithm can be performed by one application of submodular function minimization on a ring family. We also show that a rounding algorithm and a primal-dual algorithm for the submodular cost set cover problem are both constant factor approximation algorithms if the maximum frequency is fixed. In addition, we give an essentially tight lower bound on the approximability of the submodular edge cover problem.

Authors

• Satoru Iwata 0001
• Kiyohito Nagano

Keywords

• Computer science
• Submodular Function
• Submodular Function Minimization
• Estimation Algorithm
• Set Of Covariates
• Algorithm For Problem
• Undercover
• Nonnegative Function
• Coverage Problem
• Vertex Cover
• Continuous Relaxation
• Primal-dual Algorithm
• Set Cover Problem
• Cost Function
• Finite Set
• Simple Algorithm
• Perfect Match
• Feasible Set
• Case Of Problem
• Linear Order
• Special Case Of Problem
• Random Graph
• Extreme Points
• approximation algorithm
• set cover