A linear time algorithm for the r-gathering problem on the line

In this paper, we revisit the r-gathering problem. Given sets C and F of points on the plane and distance d ( c, f ) for each c ∈ C and f ∈ F, an r-gathering of C to F is an assignment A of C to open facilities F ′ ⊆ F such that r or more members of C are assigned to each open facility. The cost of an r-gathering is max c ∈ C ⁡ d ( c, A ( c ) ). The r-gathering problem computes the r-gathering minimizing the cost. In this paper we study the r-gathering problem when C and F are on a line and present a O ( | C | + | F | ) -time algorithm to solve the problem. Our solution is optimal since any algorithm needs to read C and F at least once.

Authors

• Anik Sarker
• Wing-Kin Sung
• M. Sohel Rahman

Keywords

• r-Gathering problem
• Algorithms
• Facility location problem