r-Gathering Problems on Spiders:Hardness, FPT Algorithms, and PTASes
share
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.
READ FULL TEXT