A randomized algorithm for online unit clustering

Timothy M. Chan, Hamid Zarrabi-Zadeh

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the naïve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.

Original languageEnglish (US)
Title of host publicationApproximation and Online Algorithms - 4th International Workshop, WAOA 2006, Revised Papers
Number of pages11
ISBN (Print)9783540695134
StatePublished - 2007
Externally publishedYes
Event4th Workshop on Approximation and Online Algorithms, WAOA 2006 - Zurich, Switzerland
Duration: Sep 14 2006Sep 15 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4368 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th Workshop on Approximation and Online Algorithms, WAOA 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A randomized algorithm for online unit clustering'. Together they form a unique fingerprint.

Cite this