论文标题
在有限的任务案件中
The Submodular Santa Claus Problem in the Restricted Assignment Case
论文作者
论文摘要
Goemans，Harvey，Iwata和Mirrokni（Soda'09）在一项开创性的工作中引入了圣诞老人的Santa Claus问题，以应用其结构性结果。在提到的问题中，必须将$ n $无法确定的资源分配给$ m $ players，每个播放器都具有单调suppoular实用程序函数$ f_i $。目标是最大化$ \ min_i f_i（s_i）$，其中$ s_1，\ dotsc，s_m $是资源的分区。 Goemans等人的结果。表示多项式时间$ o（n^{1/2 +\ varepsilon}）$ - 近似算法。从那时起，此问题的进展仅限于线性案例，也就是说，所有$ f_i $都是线性函数。特别是，一系列研究表明，在受限分配案例中，线性估值函数有多项式时间常数近似算法。这是给出每个播放器一组所需资源$γ_i$的特殊情况，并且单个估值功能定义为全局线性函数$ f $的$ f_i（s）= f（s \capγ_i）$。这也可以解释为最大化$ \ min_i f（s_i）$具有其他任务限制，即只能将资源分配给某些玩家。在本文中，我们为子模型变体取得了可比的进度。也就是说，如果$ f $是单调的subsodular函数，我们可以在多项式时间内计算$ o（\ log \ log \ log \ log（n））$ - 近似解决方案。
The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem $n$ unsplittable resources have to be assigned to $m$ players, each with a monotone submodular utility function $f_i$. The goal is to maximize $\min_i f_i(S_i)$ where $S_1,\dotsc,S_m$ is a partition of the resources. The result by Goemans et al. implies a polynomial time $O(n^{1/2 +\varepsilon})$-approximation algorithm. Since then progress on this problem was limited to the linear case, that is, all $f_i$ are linear functions. In particular, a line of research has shown that there is a polynomial time constant approximation algorithm for linear valuation functions in the restricted assignment case. This is the special case where each player is given a set of desired resources $Γ_i$ and the individual valuation functions are defined as $f_i(S) = f(S \cap Γ_i)$ for a global linear function $f$. This can also be interpreted as maximizing $\min_i f(S_i)$ with additional assignment restrictions, i.e., resources can only be assigned to certain players. In this paper we make comparable progress for the submodular variant. Namely, if $f$ is a monotone submodular function, we can in polynomial time compute an $O(\log\log(n))$-approximate solution.
