使用样本和隐秘性问题的竞争分析

作者：Haim Kaplan,David Naori,Danny Raz

摘要：我们扩展了标准的在线最坏情况模型，以适应过去在许多实际场景中可供在线玩家使用的体验。我们通过提前向在线玩家展示对抗性输入的随机样本来做到这一点。在线播放器与在线到达的输入部分的预期最佳值竞争。我们的模型在现有的在线随机模型（例如，从分布中i.i.d中绘制的项目）和在线最坏情况模型之间架起桥梁。我们也以类似的方式（通过揭示样本）扩展在线随机顺序模型。

我们在新模型中研究经典秘书问题。在最坏情况模型中，我们提出了一种简单的在线算法，对任何样本大小都具有最佳竞争比率。在随机顺序模型中，我们还提供了一个简单的在线算法，对于小样本量，其竞争比率几乎是紧张的。有趣的是，我们证明，对于足够大的样本，在最差投射和随机序列模型中，没有算法可以同时最优。

原文标题：Competitive Analysis with a Sample and the Secretary Problem

原文摘要：We extend the standard online worst-case model to accommodate past experience which is available to the online player in many practical scenarios. We do this by revealing a random sample of the adversarial input to the online player ahead of time. The online player competes with the expected optimal value on the part of the input that arrives online. Our model bridges between existing online stochastic models (e.g., items are drawn i.i.d. from a distribution) and the online worst-case model. We also extend in a similar manner (by revealing a sample) the online random-order model.

We study the classical secretary problem in our new models. In the worst-case model we present a simple online algorithm with optimal competitive-ratio for any sample size. In the random-order model, we also give a simple online algorithm with an almost tight competitive-ratio for small sample sizes. Interestingly, we prove that for a large enough sample, no algorithm can be simultaneously optimal both in the worst-cast and random-order models.

地址：https://arxiv.org/abs/1907.05350