The Non-Uniform k-Center Problem

In this paper, we introduce and study the Non-Uniform k-Center problem (NUkC). Given a finite metric space (X,d) and a collection of balls of radii {r1≥⋯≥rk}, the NUkC problem is to find a placement of their centers on the metric space and find the minimum dilation α, such that the union of balls of radius α⋅ri around the ith center covers all the points in X. This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds.
The NUkC problem generalizes the classic k-center problem when all the k radii are the same (which can be assumed to be 1 after scaling). It also generalizes the k-center with outliers (kCwO) problem when there are k balls of radius 1 and ℓ balls of radius 0. There are 2-approximation and 3-approximation algorithms known for these problems respectively; the former is best possible unless P=NP and the latter remains unimproved for 15 years.
We first observe that no O(1)-approximation is to the optimal dilation is possible unless P=NP, implying that the NUkC problem is more non-trivial than the above two problems. Our main algorithmic result is an (O(1),O(1))-bi-criteria approximation result: we give an O(1)-approximation to the optimal dilation, however, we may open Θ(1) centers of each radii. Our techniques also allow us to prove a simple (uni-criteria), optimal 2-approximation to the kCwO problem improving upon the long-standing 3-factor. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees which have been studied recently in the TCS community.