Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem

Minimum Submodular Cost Submodular Cover problem (MIN-SCSC) often occurs naturally in the areas of combinatorial optimization and particularly machine learning. It is well-known that the greedy algorithm proposed by Wan et al. yields a rho H(delta)-approximation for an integer-valued submodular function f, where rho is the curvature of submodular cost function c, delta is the maximum value of f over all singletons and H(delta) is the delta-th harmonic number (Wan et al. in Comput Optim Appl 45(2):463-474). In this paper, we first extend MIN-SCSC to Minimum Submodular Cost Nonsubmodular Cover problem and analyze the performances of the widely used greedy algorithm for integer-valued and fraction-valued potential functions respectively. In addition, we also study MIN-SCSC with fraction-valued potential functions, with a new analysis of the performance ratio of the greedy algorithm, improving upon the result of Wan et al. (2010).

Automated summary

This paper investigates the Minimum Submodular Cost Submodular Cover problem and the Minimum Submodular Cost Nonsubmodular Cover problem, and analyzes the performances of the greedy algorithm for integer-valued and fraction-valued potential functions.