论文标题
在线笔测试
Online Pen Testing
论文作者
论文摘要
我们研究了一个“笔测试”问题，其中为我们提供了$ n $ pens的墨水$ x_1，x_2，\ ldots，x_n $，我们想选择一支具有最大剩余墨水的笔。挑战是我们无法直接访问每个$ x_i $；我们只能用$ i $ -th的笔来编写，直到使用一定量的墨水或笔含有墨水为止。在这两种情况下，此测试都会减少笔中的剩余墨水，从而减少选择它的效用。 尽管缺乏信息，但我们表明，可以将我们的实用程序大致最大化至$ O（\ log n）$ factor。正式地，我们考虑两种不同的设置：“先知”设置，其中每个$ x_i $都是从某个分布$ \ nathcal {d} _i $的分布中独立绘制的，而“秘书”设置，其中$（x_i）_ {i = 1}^n $是随机的$ a_1 $ a_1 $ a_1，a_2，a_2，a_2 $ n $ a_2 $ n $ n $。我们在两种设置中得出最佳的竞争比率达到了恒定因素。我们的算法令人惊讶地鲁棒：（1）在先知设置中，我们只需要每个$ \ Mathcal {d} _i $中的一个样本，而不是对分布的完整描述； （2）在秘书机构中，如果给出了最大$ a_i $的估计值，则该算法也会在任意排列下成功。 我们的技术包括来自长度未知的序列的非平凡的在线抽样方案，以及在排列上建造硬，不均匀的分布。两者都可能具有独立的兴趣。我们还强调了一些即时的开放问题，并讨论了未来研究的几个方向。
We study a "pen testing" problem, in which we are given $n$ pens with unknown amounts of ink $X_1, X_2, \ldots, X_n$, and we want to choose a pen with the maximum amount of remaining ink in it. The challenge is that we cannot access each $X_i$ directly; we only get to write with the $i$-th pen until either a certain amount of ink is used, or the pen runs out of ink. In both cases, this testing reduces the remaining ink in the pen and thus the utility of selecting it. Despite this significant lack of information, we show that it is possible to approximately maximize our utility up to an $O(\log n)$ factor. Formally, we consider two different setups: the "prophet" setting, in which each $X_i$ is independently drawn from some distribution $\mathcal{D}_i$, and the "secretary" setting, in which $(X_i)_{i=1}^n$ is a random permutation of arbitrary $a_1, a_2, \ldots, a_n$. We derive the optimal competitive ratios in both settings up to constant factors. Our algorithms are surprisingly robust: (1) In the prophet setting, we only require one sample from each $\mathcal{D}_i$, rather than a full description of the distribution; (2) In the secretary setting, the algorithm also succeeds under an arbitrary permutation, if an estimate of the maximum $a_i$ is given. Our techniques include a non-trivial online sampling scheme from a sequence with an unknown length, as well as the construction of a hard, non-uniform distribution over permutations. Both might be of independent interest. We also highlight some immediate open problems and discuss several directions for future research.
