4L-01

On r-gatherings on the Line

An r-gathering of customers C to facilities F is an assignment A of C to open facilities F′⊂ F such that r or more customers areassigned to each open facility.The min-max version of the r-gathering problem finds an r-gathering having a designated minimum cost.We present an O((|C| + |F|) log(|C| + |F|)) time algorithm to solve the r-gathering problem when all C and F are on the real line.