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.

The dispersion problem is a variant of the facility location problem. Given a set P of n points and an integer k, we intend to find a subset S of P with |S|=k such that the cost minp∈S{cost(p)} is maximized, where cost(p) is the sum of the distances from p to the nearest c points in S. We call the problem the dispersion problem with partial c sum cost, or the PcS-dispersion problem. In this paper we present two algorithms to solve the P2S-dispersion problem(c=2) if all points of P are on a line. The running times of the algorithms are O(kn2 log n) and O(n log n), respectively. We also present an algorithm to solve the PcS-dispersion problem if all points of P are on a line. The running time of the algorithm is O(knc+1).

An r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊂ F such that r (≥ 2) or more customers are assigned to each open facility. (Each facility needs enough number of customers for its opening.) Then the r-gathering problem finds an r-gathering minimizing a designated cost. Armon gave a simple 3-approximation algorithm for the r-gathering problem and proved that with assumption P ≠ NP the problem cannot be approximated within a factor of less than 3 for any r ≥ 3. The running time of the 3-approximation algorithm is O(|C||F|+r|C|+|C|log|C|)). In this paper we improve the running time of the algorithm by (1) removing the sort in the algorithm and (2) designing a simple but efficient data structure.