论文标题
随着时间的流逝，先知的质量
Prophet-Inequalities over Time
论文作者
论文摘要
在本文中，我们介绍了I.I.D.众所周知的先知疾病的加班变体。随机变量。我们没有在过程中的某个时刻停止一个实现的值，而是决定每个步骤选择该值的时间。然后，在此期间结束之前，我们无法选择其他值。目标是最大化选定值之和的期望。我们描述了最佳停止规则的结构，并在先知 - 质量上给出上和下限。 - 在线算法术语中，这与在线算法的竞争比率相对应。 我们提供了一种令人惊讶的简单算法，并具有一个单个阈值，使所有输入长度$ n $的先知 - 质量约为0.396美元。此外，作为我们的主要结果，我们提出了更高级的算法，导致$ \ $ \ \ \ $ \ 0.598 $的先知质量趋于无穷大。我们通过上限来补充我们的结果，表明最好的先知 - 最多是$ 1/φ\ of 0.618 $，其中$φ$表示黄金比率。作为证明的一部分，我们对加权中的高级进行了高级限制。
In this paper, we introduce an over-time variant of the well-known prophet-inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide for each step how long we select the value. Then we cannot select another value until this period is over. The goal is to maximize the expectation of the sum of selected values. We describe the structure of the optimal stopping rule and give upper and lower bounds on the prophet-inequality. - Which, in online algorithms terminology, corresponds to bounds on the competitive ratio of an online algorithm. We give a surprisingly simple algorithm with a single threshold that results in a prophet-inequality of $\approx 0.396$ for all input lengths $n$. Additionally, as our main result, we present a more advanced algorithm resulting in a prophet-inequality of $\approx 0.598$ when the number of steps tends to infinity. We complement our results by an upper bound that shows that the best possible prophet-inequality is at most $1/φ\approx 0.618$, where $φ$ denotes the golden ratio. As part of the proof, we give an advanced bound on the weighted mediant.
