In this paper we develop streaming algorithms for the diameter problem and the k-center 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(N^{1/3}) space. For the k-center 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 2-center problem that achieves an approximation ratio of less than 4 requires Omega(N^{1/3}) space.

Diameter and k-center in sliding windows / Cohen-Addad, Vincent; Schwiegelshohn, Chris; Sohler, Christian. - 55:(2016). (Intervento presentato al convegno 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 tenutosi a Rome; Italy nel 2016) [10.4230/LIPIcs.ICALP.2016.19].

Diameter and k-center in sliding windows

Schwiegelshohn, Chris
;
2016

Abstract

In this paper we develop streaming algorithms for the diameter problem and the k-center 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(N^{1/3}) space. For the k-center 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 2-center problem that achieves an approximation ratio of less than 4 requires Omega(N^{1/3}) space.
2016
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Diameter; K-Center; Sliding Windows; Streaming
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Diameter and k-center in sliding windows / Cohen-Addad, Vincent; Schwiegelshohn, Chris; Sohler, Christian. - 55:(2016). (Intervento presentato al convegno 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 tenutosi a Rome; Italy nel 2016) [10.4230/LIPIcs.ICALP.2016.19].
File allegati a questo prodotto
File Dimensione Formato  
Cohen-Addad_Diameter-and-k-center_2016.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 531.47 kB
Formato Adobe PDF
531.47 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1085847
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? ND
social impact