On min–max r-gatherings

We consider a min–max version of the previously studied r-gathering problem with unit-demands. The problem we consider is a metric facility-location problem, in which each open facility must serve at least r customers, and the maximum of all the facility- and connection-costs should be minimized (rather than their sum). This problem is motivated by scenarios in which r customers are required for a facility to be worth opening, and the costs represent the time until the facility/connection will be available (i.e., we want to have the complete solution ready as soon as possible).We present a 3-approximation algorithm for this problem, and prove that it cannot be approximated better (assuming P≠NP). Next we consider this problem with the additional natural requirement that each customer will be assigned to a nearest open facility, and present a 9-approximation algorithm. We further consider previously introduced special cases and variants, and obtain improved algorithmic and hardness results.