On r-Gatherings on the Line
Toshihiro Akagi, Shin-ichi Nakano · IEICE Transactions on Information and Systems · 2017
In this paper we study a recently proposed variant of the facility location problem, called the r-gathering problem. Given an integer r, a set C of customers, a set F of facilities, and a connecting cost co(c, f) for each pair of c ∈ C and f ∈ F, an r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊆ F such that at least r customers are assigned to each open facility. We give an algorithm to find an r-gathering with the minimum cost, where the cost is maxc ∈ C{co(c, A(c))}, when all C and F are on the real line.