Unified Greedy Approximability beyond Submodular Maximization
SIAM Journal on Discrete Mathematics · 31.03.2024 · 38 (1) · 348-379
DOI: 10.1137/22m1526952 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 18.01.2024. Verfasst von Yann Disser und 1 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 30 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.
Abstract (Originalsprache)
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].
Förderung
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Disser, Y., & Weckbecker, D. (2024). Unified Greedy Approximability beyond Submodular Maximization. SIAM Journal on Discrete Mathematics, 38(1), 348-379. https://doi.org/10.1137/22m1526952
Vancouver
Disser Y, Weckbecker D. Unified Greedy Approximability beyond Submodular Maximization. SIAM Journal on Discrete Mathematics. 2024;38(1):348-379. doi:10.1137/22m1526952
BibTeX
@article{Disser2024,
author = {Disser, Yann and Weckbecker, David},
title = {Unified Greedy Approximability beyond Submodular Maximization},
journal = {SIAM Journal on Discrete Mathematics},
year = {2024},
volume = {38},
number = {1},
pages = {348--379},
doi = {10.1137/22m1526952}
}
EUVIMED