Better Bounds on Online Unit Clustering

Martin R. Ehmsen, Kim Skak Larsen

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

Abstract

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
PublisherSpringer
Publication date2010
Pages371-382
DOIs
Publication statusPublished - 2010
EventSWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory - Bergen, Norway
Duration: 21. Jun 201023. Jun 2010

Conference

ConferenceSWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory
Country/TerritoryNorway
CityBergen
Period21/06/201023/06/2010
SeriesLecture Notes in Computer Science
Volume6139

Fingerprint

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

Cite this