Back to Search
Start Over
UNIFIED GREEDY APPROXIMABILITY BEYOND SUBMODULAR MAXIMIZATION.
- Source :
-
SIAM Journal on Discrete Mathematics . 2024, Vol. 38 Issue 1, p348-379. 32p. - Publication Year :
- 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 γ -β -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 α/γeα/eα-1 \mathrm{e}α 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 α -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 \alpha -augmentable functions for all \α 1. For weighted rank functions of independence systems, our tight bound becomes α, which recovers the known bound of 1/q for independence systems of rank quotient at least q. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GREEDY algorithms
*APPROXIMATION algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 38
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 177075450
- Full Text :
- https://doi.org/10.1137/22M1526952