Unified greedy approximability beyond submodular maximization

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 $\gamma$-$\alpha$-augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, $\alpha$-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 $\frac{\alpha }{\gamma }\cdot \frac{{\mathrm{e}}^{\alpha }}{{\mathrm{e}}^{\alpha }-1}$ on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for $\alpha$-augmentable functions. In paritcular, as a by-product, we close a gap left in [Math.Prog., 2020] by obtaining a tight lower bound for $\alpha$-augmentable functions for all $\alpha \ge 1$. For weighted rank functions of independence systems, our tight bound becomes $\frac{\alpha }{\gamma }$, which recovers the known bound of $1/q$ for independence systems of rank quotient at least $q$.