Prophet Secretary

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10316180" target="_blank" >RIV/00216208:11320/15:10316180 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-662-48350-3_42" target="_blank" >http://dx.doi.org/10.1007/978-3-662-48350-3_42</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-48350-3_42" target="_blank" >10.1007/978-3-662-48350-3_42</a>

Result language
angličtina
Original language name
Prophet Secretary
Original language description
Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of 1/e approximate to 0.36 In this paper, we introduce prophet secretary, a natural combination of the prophet inequality and the secretary problems. We show that by using a single uniform threshold one cannot break the 0.5 barrier of the prophet inequality for the prophet secretary problem. However, we show that -using n distinct non-adaptive thresholds one can obtain a competitive ratio t
Czech name
—
Czech description
—

Project
<a href="/en/project/GA14-10003S" target="_blank" >GA14-10003S: Restricted computations: Algorithms, models, complexity</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)