Better Bounds on Online Unit Clustering

Martin R. Ehmsen, Kim Skak Larsen

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelTwelfth Scandinavian Symposium and Workshops on Algorithm Theory
Antal sider12
ForlagSpringer
Publikationsdato2010
Sider371-382
DOI
StatusUdgivet - 2010
BegivenhedSWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory - Bergen, Norge
Varighed: 21. jun. 201023. jun. 2010

Konference

KonferenceSWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory
LandNorge
ByBergen
Periode21/06/201023/06/2010
NavnLecture Notes in Computer Science
Vol/bind6139

Citationsformater

Ehmsen, M. R., & Larsen, K. S. (2010). Better Bounds on Online Unit Clustering. I Twelfth Scandinavian Symposium and Workshops on Algorithm Theory (s. 371-382). Springer. Lecture Notes in Computer Science, Bind. 6139 https://doi.org/10.1007/978-3-642-13731-0_35