A linear time algorithm for the r-gathering problem on the line.

In this paper, we revisit the r -gathering problem. Given sets C and F of points on the plane and distance d (c , f) for each c ∈ C and f ∈ F , an r -gathering of C to F is an assignment A of C to open facilities F ′ ⊆ F such that r or more members of C are assigned to each open facility. The cost of an r -gathering is max c ∈ C ⁡ d (c , A (c)). The r -gathering problem computes the r -gathering minimizing the cost. In this paper we study the r -gathering problem when C and F are on a line and present a O (| C | + | F |) -time algorithm to solve the problem. Our solution is optimal since any algorithm needs to read C and F at least once. [ABSTRACT FROM AUTHOR]