论文标题
背包秘书与爆发对手
Knapsack Secretary with Bursty Adversary
论文作者
论文摘要
随机订单或秘书模型是在线算法的最受欢迎的案例模型之一。尽管它避免了传统对抗模型的悲观情绪，但实际上，我们不能指望输入以完全随机的顺序呈现。这激发了人们对``两全其美的''的研究（纯粹和纯粹的对抗性输入的算法'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''纯粹和纯粹的对抗性输入都具有良好的性能），甚至更好，甚至更好的是，这些输入既是随机和对抗性部分的混合物。不幸的是，后者似乎很难实现，这种类型的结果很少。 为了促进我们对设计这种强大算法的理解，我们提出了一个随机阶模型，并具有一系列对抗性时间步骤。在许多情况下，意外模式爆发的假设通常是合理的，因为更改（例如对善的需求中的尖峰）通常是由常见的外部事件触发的。然后，我们考虑了此模型中的背包秘书问题：有一个尺寸$ k $的背包（例如，可用数量的商品数量），并且在每个项目的$ N $时间步骤中，其价值和大小为$ [0,1] $，并且算法需要做出不可撤销的决定，无论接受或拒绝物品。 我们设计了一种算法，当$ 1- \ tilde {o}（γ/k）$的近似值时，当对抗时间步骤可以由$ \ \ tilde $ \ tilde {o}（O}（O}（O}（O}（\ frac frac {n} n} {n} {k k}）），$γ\ ge \ ge \ ge \ ge \ ge \ sqrt {k} $。特别是，设置$γ= \ sqrt {k} $给出$（1-o（\ frac {\ ln^2 k} {\ sqrt {k}}））$ - 近似值，可抵抗可抵抗$ \ frac {\ ln^2 k} $ frac {\ ln^2 k} $ frac {即使没有对抗性物品，也几乎是最佳的。另外，设置$γ= \tildeΩ（k）$给出了恒定近似，该近似可抵抗对对抗性的恒定分数。
The random-order or secretary model is one of the most popular beyond-worst case model for online algorithms. While it avoids the pessimism of the traditional adversarial model, in practice we cannot expect the input to be presented in perfectly random order. This has motivated research on ``best of both worlds'' (algorithms with good performance on both purely stochastic and purely adversarial inputs), or even better, on inputs that are a mix of both stochastic and adversarial parts. Unfortunately the latter seems much harder to achieve and very few results of this type are known. Towards advancing our understanding of designing such robust algorithms, we propose a random-order model with bursts of adversarial time steps. The assumption of burstiness of unexpected patterns is reasonable in many contexts, since changes (e.g. spike in a demand for a good) are often triggered by a common external event. We then consider the Knapsack Secretary problem in this model: there is a knapsack of size $k$ (e.g., available quantity of a good), and in each of the $n$ time steps an item comes with its value and size in $[0,1]$ and the algorithm needs to make an irrevocable decision whether to accept or reject the item. We design an algorithm that gives an approximation of $1 - \tilde{O}(Γ/k)$ when the adversarial time steps can be covered by $Γ\ge \sqrt{k}$ intervals of size $\tilde{O}(\frac{n}{k})$. In particular, setting $Γ= \sqrt{k}$ gives a $(1 - O(\frac{\ln^2 k}{\sqrt{k}}))$-approximation that is resistant to up to a $\frac{\ln^2 k}{\sqrt{k}}$-fraction of the items being adversarial, which is almost optimal even in the absence of adversarial items. Also, setting $Γ= \tildeΩ(k)$ gives a constant approximation that is resistant to up to a constant fraction of items being adversarial.
