EUVIMEDEUVIMED entdecken
Crossref

Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue

Zhiyi Huang, Qiankun Zhang

SIAM Journal on Computing · 31.10.2024 · 53 (5) · 1217-1256

DOI: 10.1137/21m1454705 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 04.09.2024. Verfasst von Zhiyi Huang und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 33 Literaturangaben. Gefördert von: Research Grants Council of Hong Kong, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Mehta and Panigrahi ( FOCS 2012, IEEE, Piscataway, NJ, 2012, pp. 728–737) introduce the problem of online matching with stochastic rewards, where edges are associated with success probabilities and a match succeeds with the probability of the corresponding edge. It is one of the few online matching problems that have defied the randomized online primal dual framework by Devanur, Jain, and Kleinberg ( SODA 2013, SIAM, Philadelphia, 2013, pp. 101–107) thus far. This paper unlocks the power of randomized online primal dual in online matching with stochastic rewards by employing the configuration linear program rather than the standard matching linear program used in previous works. Our main result is a 0.572 competitive algorithm for the case of vanishing and unequal probabilities, improving the best previous bound of 0.534 by Mehta, Waggoner, and Zadimoghaddam ( SODA 2015, SIAM, Philadelphia, 2015, pp. 1388–1404) and, in fact, is even better than the best previous bound of 0.567 by Mehta and Panigrahi ( FOCS 2012, IEEE, Piscataway, NJ, 2012, pp. 728–737) for the more restricted case of vanishing and equal probabilities. For vanishing and equal probabilities, we get a better competitive ratio of 0.576. Our results further generalize to the vertex-weighted case due to the intrinsic robustness of the randomized online primal dual analysis.

Förderung

  • Research Grants Council of Hong Kong
  • National Natural Science Foundation of China

Zitieren

APA

Huang, Z., & Zhang, Q. (2024). Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue. SIAM Journal on Computing, 53(5), 1217-1256. https://doi.org/10.1137/21m1454705

Vancouver

Huang Z, Zhang Q. Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue. SIAM Journal on Computing. 2024;53(5):1217-1256. doi:10.1137/21m1454705

BibTeX
@article{Huang2024,
  author = {Huang, Zhiyi and Zhang, Qiankun},
  title = {Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue},
  journal = {SIAM Journal on Computing},
  year = {2024},
  volume = {53},
  number = {5},
  pages = {1217--1256},
  doi = {10.1137/21m1454705}
}
Kostenlos starten →