EUVIMEDEUVIMED entdecken
Crossref

Minimum Cost Adaptive Submodular Cover

Hessa Al-Thani, Yubing Cui, Blake Harris, Viswanath Nagarajan

Mathematics of Operations Research · 04.06.2026

DOI: 10.1287/moor.2024.0548 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, online erschienen am 04.06.2026. Verfasst von Hessa Al-Thani und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 38 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Adaptive submodularity is a fundamental concept in stochastic optimization, with numerous applications such as sensor placement, hypothesis identification, and viral marketing. We consider the problem of covering an adaptive submodular function at minimum expected cost, where the random realizations of different items may be correlated. We show that the natural greedy policy has an approximation ratio of [Formula: see text], where Q is the goal value. We also show that the greedy policy has approximation ratio of at least [Formula: see text] even when [Formula: see text], which invalidates a prior result on adaptive submodular cover. Moreover, we consider a significantly more general objective of minimizing the pth moment of the coverage cost and show that the greedy policy simultaneously achieves a [Formula: see text] approximation guarantee for all [Formula: see text]. All our approximation ratios are best possible up to constant factors (assuming [Formula: see text]). Our results also extend to the setting where one wants to cover multiple adaptive submodular functions, for which we obtain the same approximation guarantees. Funding: Financial support from the National Science Foundation Division of Computing and Communication Foundations [Grant 2418495] and the Qatar National Research Fund [QRDI Grant GSRA7-0419-20020] is gratefully acknowledged.

Zitieren

APA

Al-Thani, H., Cui, Y., Harris, B., & Nagarajan, V. (2026). Minimum Cost Adaptive Submodular Cover. Mathematics of Operations Research. https://doi.org/10.1287/moor.2024.0548

Vancouver

Al-Thani H, Cui Y, Harris B, Nagarajan V. Minimum Cost Adaptive Submodular Cover. Mathematics of Operations Research. 2026. doi:10.1287/moor.2024.0548

BibTeX
@article{AlThani2026,
  author = {Al-Thani, Hessa and Cui, Yubing and Harris, Blake and Nagarajan, Viswanath},
  title = {Minimum Cost Adaptive Submodular Cover},
  journal = {Mathematics of Operations Research},
  year = {2026},
  doi = {10.1287/moor.2024.0548}
}
Kostenlos starten →