.png){kind=icon}
返回
Prophet Inequalities over Time
.png){kind=icon}
PRE
AI
DOI：10.1145/3766547.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本文中，我们介绍了一种基于独立同分布随机变量的时序变体形式的著名先知不等式。与在过程中某一点以一个已实现值停止不同，我们决定在每一步选择值的时间长度。然后，直到该时段结束前，我们不能再选择其他值。目标是最大化所选值的总和的期望。我们描述了最优停止规则的结构，并给出了先知不等式的上下界。在在线算法术语中，这对应于一个在线算法的竞争比的界。我们提出了一种令人惊讶的简单算法，该算法仅使用一个阈值，对于所有输入长度，其先知不等式约为0.396。此外，作为我们的主要结果，我们介绍了一种更高级的算法，当步数趋于无穷大时，其先知不等式约为0.598。我们通过一个上界来补充我们的结果，该上界表明最佳可能的先知不等式至多为1/psi≈0.618，其中psi表示黄金比例。
Keyword:
Online algorithms
prophet inequalities
reusable resources
期刊
A
IF:
0.9
论文数:
8
被引数:
0
机构
引用论文
.png){kind=icon}
查看更多内容