论文标题
蜘蛛的收集问题：硬度，FPT算法和Ptases
r-Gathering Problems on Spiders:Hardness, FPT Algorithms, and PTASes
论文作者
论文摘要
我们考虑最低的最大$ r $ - 收集问题如下：我们在公制空间中获得了一组用户和设施。我们打开了一些设施，并将每个用户分配到打开的设施，以便每个设施至少具有$ R $用户。目标是最大程度地减少用户与分配的设施之间的最大距离。我们还考虑了Min-Max $ r $ r $ - 加法的聚类问题，这是$ r $ - 采集到各处的$ r $ - 采集问题的特殊情况。在本文中，我们研究了基础度量空间是蜘蛛的障碍性和硬度，它回答了Ahmed等人提出的开放问题。 [Walcom'19]。首先，我们表明问题是NP危险，即使基础空间是蜘蛛。然后，我们提出了以该中心的$ d $参数为参数的FPT算法。这改善了以前的算法，因为它们是由$ r $和$ d $的参数化。最后，我们向问题提出了PTases。这些是最好的，因为除非p = np，否则没有fptase。
We consider the min-max $r$-gathering problem described as follows: We are given a set of users and facilities in a metric space. We open some of the facilities and assign each user to an opened facility such that each facility has at least $r$ users. The goal is to minimize the maximum distance between the users and the assigned facility. We also consider the min-max $r$-gather clustering problem, which is a special case of the $r$-gathering problem in which the facilities are located everywhere. In this paper, we study the tractability and the hardness when the underlying metric space is a spider, which answers the open question posed by Ahmed et al. [WALCOM'19]. First, we show that the problems are NP-hard even if the underlying space is a spider. Then, we propose FPT algorithms parameterized by the degree $d$ of the center. This improves the previous algorithms because they are parameterized by both $r$ and $d$. Finally, we propose PTASes to the problems. These are best possible because there are no FPTASes unless P=NP.
