r-Gather Clustering and r-Gathering on Spider: FPT Algorithms and Hardness
share
We consider min-max r-gather clustering problem and min-max r-gathering problem. In the min-max r-gather clustering problem, we are given a set of users and divide them into clusters with size at least r; the goal is to minimize the maximum diameter of clusters. In the min-max r-gathering problem, we are additionally given a set of facilities and assign each cluster to a facility; the goal is to minimize the maximum distance between the users and the assigned facility. In this study, we consider the case that the users and facilities are located on a "spider" and propose the first fixed-parameter tractable (FPT) algorithms for both problems, which are parametrized by only the number of legs. Furthermore, we prove that these problems are NP-hard when the number of legs is arbitrarily large.
READ FULL TEXT