EUVIMEDEUVIMED entdecken
Crossref

Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations

Robert L. Bray

Operations Research · 2025-07 · 73 (4) · 2188-2203

DOI: 10.1287/opre.2022.0036 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Operations Research, 2025-07. Verfasst von Robert L. Bray. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 9 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In 2019, Alessandro Arlotto and Itai Gurvich proved that the expected regret in the multisecretary problem is uniformly bounded as the number of jobs to fill goes to infinity. However, they modeled the secretary valuation distribution as discrete and known, and they concluded their article by explaining that they did not know whether their bound would hold with continuous or unknown valuation distributions. In “Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations,” Robert L. Bray provides an answer, furnishing lower and upper bounds that demonstrate that the regret in multisecretary problem grows like the logarithm of the number of positions to fill when the distribution of secretary valuations continuous or unknown. He then develops the argument to establish analogous bounds for the more general online linear program, defined by Xiaocheng Li and Yinyu Ye. Bray tightens Li and Ye’s upper regret bound and develops a corresponding lower regret bound. To create these bounds, Bray develops several new convergence results for the online linear program’s dual variables.

Zitieren

APA

Bray, R. L. (2025). Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations. Operations Research, 73(4), 2188-2203. https://doi.org/10.1287/opre.2022.0036

Vancouver

Bray RL. Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations. Operations Research. 2025;73(4):2188-2203. doi:10.1287/opre.2022.0036

BibTeX
@article{Bray2025,
  author = {Bray, Robert L.},
  title = {Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations},
  journal = {Operations Research},
  year = {2025},
  volume = {73},
  number = {4},
  pages = {2188--2203},
  doi = {10.1287/opre.2022.0036}
}
Kostenlos starten →