论文标题
紧密的近似保证凹面问题
Tight Approximation Guarantees for Concave Coverage Problems
论文作者
论文摘要
在最大覆盖范围问题中，我们得到了$ t_1，\ ldots，t_m $ [n] $以及整数$ k $的子集，目标是找到一个子集$ s \ subseteq [m subseteq [m] size $ k $的$ k $，最大化$ C（s）这个问题的贪婪算法达到了$ 1-e^{ - 1} $的最佳近似值，这是一个经典的结果。 在这项工作中，我们考虑了此问题的概括，其中元素$ a $可以取决于涵盖次数的数量。给定一个凹面的，无折叠函数$φ$，我们定义$ c^φ（s）：= \ sum_ {a \ in [n]}w_aφ（| s | _a）$，其中$ | s | s | _a = | \ {i \ in s：in s：a \ in t_i \} in t_i \} | $。标准最大覆盖范围问题对应于$φ（j）= \ min \ {j，1 \} $。对于任何此类$φ$，我们提供了一种有效的算法，该算法达到近似值，等于$α_φ$ = \ min_ {x \ in \ mathbb {n}^*}定义的poisson凹率比为$φ$ \ frac {\ mathbb {e} [φ（\ text {poi}（x））]}} {φ（\ mathbb {e} [\ text {poi}（x）（x））}} $。在补充这种近似保证的情况下，当$φ$以sublinear的方式生长时，我们建立了一个匹配的NP硬度结果。 作为特殊情况，我们改善了[Barman等人，IPCO，2020]的结果，该结果是基于独特的游戏猜想的最大多覆盖范围，并且在基于多赢家批准的基于多赢家批准的投票中，我们恢复了[Dudycz等，IJCAI，2020年]的结果。我们的结果超出了这些特殊案例，我们将其用作分配的资源分配问题，福利最大化问题和基于批准的一般规则投票的应用程序进行了说明。
In the maximum coverage problem, we are given subsets $T_1, \ldots, T_m$ of a universe $[n]$ along with an integer $k$ and the objective is to find a subset $S \subseteq [m]$ of size $k$ that maximizes $C(S) := \Big|\bigcup_{i \in S} T_i\Big|$. It is a classic result that the greedy algorithm for this problem achieves an optimal approximation ratio of $1-e^{-1}$. In this work we consider a generalization of this problem wherein an element $a$ can contribute by an amount that depends on the number of times it is covered. Given a concave, nondecreasing function $φ$, we define $C^φ(S) := \sum_{a \in [n]}w_aφ(|S|_a)$, where $|S|_a = |\{i \in S : a \in T_i\}|$. The standard maximum coverage problem corresponds to taking $φ(j) = \min\{j,1\}$. For any such $φ$, we provide an efficient algorithm that achieves an approximation ratio equal to the Poisson concavity ratio of $φ$, defined by $α_φ := \min_{x \in \mathbb{N}^*} \frac{\mathbb{E}[φ(\text{Poi}(x))]}{φ(\mathbb{E}[\text{Poi}(x)])}$. Complementing this approximation guarantee, we establish a matching NP-hardness result when $φ$ grows in a sublinear way. As special cases, we improve the result of [Barman et al., IPCO, 2020] about maximum multi-coverage, that was based on the unique games conjecture, and we recover the result of [Dudycz et al., IJCAI, 2020] on multi-winner approval-based voting for geometrically dominant rules. Our result goes beyond these special cases and we illustrate it with applications to distributed resource allocation problems, welfare maximization problems and approval-based voting for general rules.
