@inproceedings{chakrabarty2016the,
author = {Chakrabarty, Deeparnab and Goyal, Prachi and Krishnaswamy, Ravishankar},
title = {The Non-Uniform k-Center Problem},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy},
year = {2016},
month = {July},
abstract = {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.},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
url = {http://approjects.co.za/?big=en-us/research/publication/non-uniform-k-center-problem/},
pages = {1-15},
volume = {55},
isbn = {978-3-95977-013-2},
edition = {43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy},
}