EUVIMEDEUVIMED entdecken
Crossref

Order-Competitive Ratio

Liyan Chen, Tomer Ezra, Michal Feldman, Nick Gravin, Nuozhou Sun, Zhihao Gavin Tang

SIAM Journal on Computing · 30.04.2026 · 55 (2) · 332-361

DOI: 10.1137/24m1708917 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 04.03.2026. Verfasst von Liyan Chen und 5 weiteren Autor:innen. Die Arbeit nennt 68 Literaturangaben. Gefördert von: Harvard University Center of Mathematical Sciences and Applications, Amazon, TAU Center for AI and Data Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in an online fashion. Our new measure is called an order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far. We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely, (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms, and preliminary results for randomized algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. In contrast to the classic competitive ratio measure, where the optimal performance is obtained by deterministic single-threshold algorithms, our results for order-competitive ratio capture the intuition that adaptive algorithms may be more powerful than single-threshold ones, and randomized algorithms outperform deterministic ones.

Förderung

  • Harvard University Center of Mathematical Sciences and Applications
  • Amazon
  • TAU Center for AI and Data Science
  • European Research Council
  • NSF-BSF
  • Amazon Research Award
  • Harvard University
  • Israel Science Foundation

Zitieren

APA

Chen, L., Ezra, T., Feldman, M., Gravin, N., Sun, N., & Tang, Z. G. (2026). Order-Competitive Ratio. SIAM Journal on Computing, 55(2), 332-361. https://doi.org/10.1137/24m1708917

Vancouver

Chen L, Ezra T, Feldman M, Gravin N, Sun N, Tang ZG. Order-Competitive Ratio. SIAM Journal on Computing. 2026;55(2):332-361. doi:10.1137/24m1708917

BibTeX
@article{Chen2026,
  author = {Chen, Liyan and Ezra, Tomer and Feldman, Michal and Gravin, Nick and Sun, Nuozhou and Tang, Zhihao Gavin},
  title = {Order-Competitive Ratio},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {2},
  pages = {332--361},
  doi = {10.1137/24m1708917}
}
Kostenlos starten →