A randomized algorithm for online unit clustering

Timothy M. Chan, Hamid Zarrabi-Zadeh

Research output: Contribution to journalArticlepeer-review


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)
Pages (from-to)486-496
Number of pages11
JournalTheory of Computing Systems
Issue number3
StatePublished - Jul 2009
Externally publishedYes


  • Online algorithms
  • Randomized algorithms
  • Unit clustering

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics


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

Cite this