@inproceedings{0da1ee1c569e4b6eb29c01b5b31faf83,

title = "Better Bounds on Online Unit Clustering",

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.",

author = "Ehmsen, {Martin R.} and Larsen, {Kim Skak}",

year = "2010",

doi = "10.1007/978-3-642-13731-0_35",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "371--382",

booktitle = "Twelfth Scandinavian Symposium and Workshops on Algorithm Theory",

address = "Germany",

note = "SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory ; Conference date: 21-06-2010 Through 23-06-2010",

}