On r-Gatherings on the Line

摘要

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 max_(c ∈ C ){co (c , A (c ))}, when all C and F are on the real line.