@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  and a collection of balls of radii , 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  around the th center covers all the points in . This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds. The NUkC problem generalizes the classic -center problem when all the  radii are the same (which can be assumed to be  after scaling). It also generalizes the -center with outliers (kCwO) problem when there are  balls of radius  and  balls of radius . There are -approximation and -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 -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 -bi-criteria approximation result: we give an -approximation to the optimal dilation, however, we may open  centers of each radii. Our techniques also allow us to prove a simple (uni-criteria), optimal -approximation to the kCwO problem improving upon the long-standing -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},
}