EUVIMEDEUVIMED entdecken
Crossref

Unified Greedy Approximability beyond Submodular Maximization

Yann Disser, David Weckbecker

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →