Greedy approximations for minimum submodular cover with submodular cost

摘要

It is well-known that a greedy approximation with an integer-valued polymatroid potential function f is H(γ)-approximation of the minimum submodular cover problem with linear cost where γ is the maximum value of f over all singletons and H(γ) is the γ-th harmonic number. In this paper, we establish similar results for the minimum submodular cover problem with a submodular cost (possibly nonlinear) and/or fractional submodular potential function f.