Unified Greedy Approximability beyond Submodular Maximization
Yann Disser, David Weckbecker · SIAM Journal on Discrete Mathematics · 2024
Abstract. We consider classes of objective functions of cardinality-constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of [Formula: see text]-[Formula: see text]-augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, [Formula: see text]-augmentable functions, and weighted rank functions of an independence system of bounded rank quotient—as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of [Formula: see text] on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for [Formula: see text]-augmentable functions. In particular, as a by-product, we close a gap in [A. Bernstein et al., Math. Program., 191 (2022), pp. 953–979] by obtaining a tight lower bound for [Formula: see text]-augmentable functions for all [Formula: see text]. For weighted rank functions of independence systems, our tight bound becomes [Formula: see text], which recovers the known bound of [Formula: see text] for independence systems of rank quotient at least [Formula: see text].