文章基本信息
- 标题：Optimal Single-Choice Prophet Inequalities from Samples
- 本地全文：下载
- 作者：Aviad Rubinstein ; Jack Z. Wang ; S. Matthew Weinberg 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：151
- 页码：1-10
- DOI：10.4230/LIPIcs.ITCS.2020.60
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of 1/2 can be achieved with a single sample from each distribution. When the distributions are identical, we show that for any constant ε > 0, O(n) samples from the distribution suffice to achieve the optimal competitive ratio (â^ 0.745) within (1+ε), resolving an open problem of [José R. Correa et al., 2019].
- 关键词：Online algorithms; Probability; Optimization; Prophet inequalities; Samples; Auctions
