论文标题
圣诞老人问题的在线算法
Online Algorithms for the Santa Claus Problem
论文作者
论文摘要
圣诞老人问题是公平分裂中的一个基本问题：目标是在异质代理之间分配一组异质项目，以最大程度地提高任何代理商收到的物品的最低价值。在本文中，我们研究了此问题的在线版本，其中不知道这些物品随着时间的推移而被分配给代理商。如果项目的到达顺序是任意的，则在最坏的情况下不存在好的分配规则。但是，我们表明，如果到达订单是随机的，那么对于$ n $代理和任何$ \ varepsilon> 0 $，我们可以获得$ 1- \ VAREPSILON $的竞争比率，当最佳分配给每个代理商（假设每个代理商）的值至少为每个代理商（假设每个单位价值）。我们还表明，这个结果几乎很紧：也就是说，如果最佳解决方案最多具有$ c \ ln n / \ varepsilon $，则对于某些常数$ c $，那么即使是随机到达订单，也没有$（1- \ varepsilon）$（1- \ varepsilon）$。
The Santa Claus problem is a fundamental problem in fair division: the goal is to partition a set of heterogeneous items among heterogeneous agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online version of this problem where the items are not known in advance and have to be assigned to agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment rule exists in the worst case. However, we show that, if the arrival order is random, then for $n$ agents and any $\varepsilon > 0$, we can obtain a competitive ratio of $1-\varepsilon$ when the optimal assignment gives value at least $Ω(\log n / \varepsilon^2)$ to every agent (assuming each item has at most unit value). We also show that this result is almost tight: namely, if the optimal solution has value at most $C \ln n / \varepsilon$ for some constant $C$, then there is no $(1-\varepsilon)$-competitive algorithm even for random arrival order.
