de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

On the Online Unit Clustering Problem

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45543

van Stee,  Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Epstein, L., & van Stee, R. (2010). On the Online Unit Clustering Problem. ACM Transactions on Algorithms, 7(1): 7, pp. 1-18. doi:10.1145/1868237.1868245.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-16A1-2
Abstract
We continue the study of the online unit clustering problem, introduced by Chan and Zarrabi-Zadeh (\emph{Workshop on Approximation and Online Algorithms 2006}, LNCS 4368, p.121--131. Springer, 2006). We design a deterministic algorithm with a competitive ratio of $7/4$ for the one-dimensional case. This is the first deterministic algorithm that beats the bound of 2. It also has a better competitive ratio than the previous randomized algorithms. Moreover, we provide the first non-trivial deterministic lower bound, improve the randomized lower bound, and prove the first lower bounds for higher dimensions.