CohenAddad, Vincent ;
Schwiegelshohn, Chris ;
Sohler, Christian
Diameter and kCenter in Sliding Windows
Abstract
In this paper we develop streaming algorithms for the diameter problem and the kcenter clustering problem in the sliding window model. In this model we are interested in maintaining a solution for the N most recent points of the stream. In the diameter problem we would like to maintain two points whose distance approximates the diameter of the point set in the window. Our algorithm computes a (3 + epsilon)approximation and uses O(1/epsilon*ln(alpha)) memory cells, where alpha is the ratio of the largest and smallest distance and is assumed to be known in advance. We also prove that under reasonable assumptions obtaining a (3  epsilon)approximation requires Omega(N1/3) space.
For the kcenter problem, where the goal is to find k centers that minimize the maximum distance of a point to its nearest center, we obtain a (6 + epsilon)approximation using O(k/epsilon*ln(alpha)) memory cells and a (4 + epsilon)approximation for the special case k = 2. We also prove that any algorithm for the 2center problem that achieves an approximation ratio of less than 4 requires Omega(N^{1/3}) space.
BibTeX  Entry
@InProceedings{cohenaddad_et_al:LIPIcs:2016:6340,
author = {Vincent CohenAddad and Chris Schwiegelshohn and Christian Sohler},
title = {{Diameter and kCenter in Sliding Windows}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {19:119:12},
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/6340},
URN = {urn:nbn:de:0030drops63401},
doi = {10.4230/LIPIcs.ICALP.2016.19},
annote = {Keywords: Streaming, kCenter, Diameter, Sliding Windows}
}
23.08.2016
Keywords: 

Streaming, kCenter, Diameter, Sliding Windows 
Seminar: 

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

Issue date: 

2016 
Date of publication: 

23.08.2016 