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 \({r_1\geq \cdots \geq r_k}\), the NUkC problem is to find a placement of their centers on the metric space and find the minimum dilation \(\alpha\), such that the union of balls of radius \(\alpha \cdot r_i\) around the \(i\)th 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 \(\Theta (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.