Unified Greedy Approximability Beyond Submodular Maximization
1 : TU Darmstadt
We consider classes of objectivs 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 includes several important subclasses, such as functions of bounded submodularity ratio, $\alpha$-augmentable functions, and weighted rank functions of independence systems. We show a tight bound of $\frac{\alpha e^\alpha}{\gamma(e^\alpha-1)}$ on the approximation ratio of the greedy algorithm that recovers the bounds known for previously mentioned function classes. As a by-product, we obtain a tight lower bound for $\alpha$-augmentable functions.