论文标题
改进的度量电容覆盖问题的界限
Improved Bounds for Metric Capacitated Covering Problems
论文作者
论文摘要
在指标电容覆盖（MCC）问题中，给定一组球$ \ Mathcal {b} $在公制空间$ p $带有公制$ d $和容量参数$ u $的情况下，目标是找到一个最小尺寸的子集$ \ Mathcal $ \ Mathcal {b}'\ seteq \ seteq \ seteq \ natercal and prom in compote and points in togipt in Comption and coption and coption in Cosity in Cosity of Prime and to in Cosity in Cosity of Pers of Ancopt $ \ MATHCAL {B}'$，以便将每个点分配给包含它的球，并且每个球最多都会分配给最多$ U $点。 MCC使用贪婪算法实现$ O（\ log | p |）$ - 近似。另一方面，即使是$β<3 $ kluption the Balls，也很难在$ o（\ log | p |）$（\ log | p |）$之内近似。 Bandyapadhyay〜 {等} [SOCG 2018，DCG 2019]表明，可以通过$ 6.47 $ $ o（1）$ - 近似球获得$ 6.47 $ $ 6.47 $。他们的工作剩下的一个空旷的问题是减少下限$ 3 $和上限$ 6.47 $之间的差距。在目前的工作中，我们表明可以获得$ O（1）$ - 仅$ 4.24 $ $ $ o（1）$ 4.24 $。我们还显示了更概括的MCC版本的$ 5 $的上限，以前最著名的限制为$ 9 $。
In the Metric Capacitated Covering (MCC) problem, given a set of balls $\mathcal{B}$ in a metric space $P$ with metric $d$ and a capacity parameter $U$, the goal is to find a minimum sized subset $\mathcal{B}'\subseteq \mathcal{B}$ and an assignment of the points in $P$ to the balls in $\mathcal{B}'$ such that each point is assigned to a ball that contains it and each ball is assigned with at most $U$ points. MCC achieves an $O(\log |P|)$-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of $o(\log |P|)$ even with $β< 3$ factor expansion of the balls. Bandyapadhyay~{et al.} [SoCG 2018, DCG 2019] showed that one can obtain an $O(1)$-approximation for the problem with $6.47$ factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound $3$ and the upper bound $6.47$. In this current work, we show that it is possible to obtain an $O(1)$-approximation with only $4.24$ factor expansion of the balls. We also show a similar upper bound of $5$ for a more generalized version of MCC for which the best previously known bound was $9$.
