A Simple Algorithm for $r$-gatherings on the Line
Shin-ichi Nakano · Journal of Graph Algorithms and Applications · 2019
In this paper we study a recently proposed variant of the facility location problem called the $r$-gathering problem. Given sets $C$ and $F$ of points on the plane and distance $d(c,f)$ for each $c\in C$ and $f\in F$, an $r$-gathering of $C$ to $F$ is an assignment $A$ of $C$ to facilities $F^{'} \subset F$ such that $r$ or more customers are assigned to each facility in $F^{'}$. A facility is open in $A$ if at least one customer is assigned to it. The cost of an $r$-gathering is the maximum distance $d(c,f)$ between $c\in C$ and $A(c)\in F'$ among the assignment, which is $\max_{c\in C}\{ d(c,A(c)) \}$. The $r$-gathering problem finds the $r$-gathering that minimizes the cost. When all points of $C$ and $F$ are on the line, an $O((|C|+|F|)\log (|C|+|F|) )$-time algorithm and an $O(|C|+|F|\log^2 r+|F|\log|F|)$-time algorithm to solve the $r$-gathering problem are known. In this paper we give a simple $O(|C|+r^2|F|)$-time algorithm to solve the $r$-gathering problem. Since $r