@inproceedings{abolhassani2017beating,
author = {Abolhassani, Melika and Ehsani, Soheil and Esfandiari, Hossein and Hajiaghayi, MohammadTaghi and Kleinberg, Robert and Lucier, Brendan},
title = {Beating 1-1/e for ordered prophets},
booktitle = {STOC 2017},
year = {2017},
month = {June},
abstract = {Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 − 1/e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is 1/1+1/e≃ 0.731. This conjecture remained open prior to this paper for over 30 years. In this paper we present a threshold-based algorithm for the prophet inequality with n iid distributions. Using a nontrivial and novel approach we show that our algorithm is a 0.738-approximation algorithm. By beating the bound of 1/1+1/e, this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-uniform distributions and discuss its applications in mechanism design.},
url = {http://approjects.co.za/?big=en-us/research/publication/beating-1-1-e-ordered-prophets/},
}