Better Bounds on Online Unit Clustering

Martin R. Ehmsen, Kim Skak Larsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


Unit Clustering is the problem of dividing a set of points from a metric space into a minimal number of subsets such that the points in each subset are enclosable by a unit ball. We continue work initiated by Chan and Zarrabi-Zadeh on determining the competitive ratio of the online version of this problem. For the one-dimensional case, we develop a deterministic algorithm, improving the best known upper bound of 7/4 by Epstein and van Stee to 5/3. This narrows the gap to the best known lower bound of 8/5 to only 1/15. Our algorithm automatically leads to improvements in all higher dimensions as well. Finally, we strengthen the deterministic lower bound in two dimensions and higher from 2 to 13/6.
Original languageEnglish
Title of host publicationTwelfth Scandinavian Symposium and Workshops on Algorithm Theory
Number of pages12
Publication date2010
Publication statusPublished - 2010
EventSWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory - Bergen, Norway
Duration: 21. Jun 201023. Jun 2010


ConferenceSWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Better Bounds on Online Unit Clustering'. Together they form a unique fingerprint.

Cite this