◎赤木俊裕・中野眞一（群馬大）

Given two integers k and r, a set of customer locations C, and a set of potential facility locations F, we wish to compute an assignment A of C to F such that (1) for each c ∈ C the distance between c and A(c) ∈ F is at most k, and (2) for each f ∈ F the number of customers assigned to f is either zero, or at least r. Such an assignment is called a (k,r)-gathering of C to F.
In this paper we solve the problem in linear time when the customer locations and potential facility locations are on a line.