Prophet and Secretary at the Same Time
Gregory Kehne and Thomas Kesselheim
许多在线问题在随机设置中进行研究,其中输入是预先给出的已知分布的样本,或来自未知分布的样本。 这种分布模型既超越了最坏情况的输入,也模拟了在线算法的部分预知。 但是,这种算法对给定分布的错误排序有多强? 什么时候可以检测到,什么时候重要? 当输入分布按规定进行时,算法何时可以给出良好的竞争比例? 我们在最优停止的设置中考虑这些问题,其中已知和未知分布的情况分别对应于众所周知的先知不平等和秘书问题。 在这里,我们问:停止规则是否同时对先知不平等问题和秘书问题有竞争力? 我们限制了帕累托边疆同时近似比(α,β),一个停止规则可以达到。 我们引入了一系列算法,这些算法提供非平凡的联合保证,并且对于极端的i.i.d.先知和秘书问题是最佳的。 我们还证明不可能,识别(α,β)无法通过任何适应性停止规则。 我们的结果适用于 n 固定抵达者和来自 Poisson 流程的抵达者,费率为 n。 我们主要在Poisson环境中工作,并在Poisson和N-到达设置之间提供可能具有更广泛兴趣的减少。
Many online problems are studied in stochastic settings for which inputs are samples from a known distribution, given in advance, or from an unknown distribution. Such distributions model both beyond-worst-case inputs and, when given, partial foreknowledge for the online algorithm. But how robust can such algorithms be to misspecification of the given distribution? When is this detectable, and when does it matter? When can algorithms give good competitive ratios both when the input distribution ...
