Chakrabarty, Deeparnab ;
Goyal, Prachi ;
Krishnaswamy, Ravishankar
The NonUniform kCenter Problem
Abstract
In this paper, we introduce and study the NonUniform kCenter (NUkC) problem. Given a finite metric space (X, d) and a collection of balls of radii {r_1 >= ... >= 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*r_i around the ith center covers all the points in X. This problem naturally arises as a minmax vehicle routing problem with fleets of different speeds, or as a wireless router placement problem with routers of different powers/ranges.
The NUkC problem generalizes the classic kcenter problem when all the k radii are the same (which can be assumed to be 1 after scaling). It also generalizes the kcenter with outliers (kCwO for short) problem when there are k balls of radius 1 and l balls of radius 0. There are 2approximation and 3approximation 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 nontrivial than the above two problems. Our main algorithmic result is an (O(1), O(1))bicriteria 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 (unicriteria), optimal 2approximation to the kCwO problem improving upon the longstanding 3factor. Our main technical contribution is a connection between the NUkC problem and the socalled firefighter problems on trees which have been studied recently in the TCS community. We show NUkC is as hard as the firefighter problem.
While we don't know if the converse is true, we are able to adapt ideas from recent works [Chalermsook/Chuzhoy, SODA 2010; Asjiashvili/Baggio/Zenklusen, arXiv 2016] in nontrivial ways to obtain our constant factor bicriteria approximation.
BibTeX  Entry
@InProceedings{chakrabarty_et_al:LIPIcs:2016:6217,
author = {Deeparnab Chakrabarty and Prachi Goyal and Ravishankar Krishnaswamy},
title = {{The NonUniform kCenter Problem}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {67:167:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6217},
URN = {urn:nbn:de:0030drops62178},
doi = {10.4230/LIPIcs.ICALP.2016.67},
annote = {Keywords: Clustering, kCenter, Approximation Algorithms, Firefighter Problem}
}
23.08.2016
Keywords: 

Clustering, kCenter, Approximation Algorithms, Firefighter Problem 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 