Paper Info
Title
An Improved Algorithm for Online Unit Clustering
Abstract
We revisit the online unit clustering problem in one dimen- sion which we recently introduced at WAOA'06: given a sequence of n points on the line, the objective is to partition the points into a mini- mum number of subsets, each enclosable by a unit interval. We present a new randomized online algorithm that achieves expected competitive ratio 11/6 against oblivious adversaries, improving the previous ratio of 15/8. This immediately leads to improved upper bounds for the problem in two and higher dimensions as well.
Year
DOI
Venue
2007
10.1007/s00453-008-9208-9
Computing and Combinatorics
Keywords
DocType
Volume
Online algorithms,Randomized algorithms,Unit clustering
Conference
54
Issue
ISSN
ISBN
4
0178-4617
3-540-73544-5
Citations 
PageRank 
References 
7
0.64
11
Authors
2
Name
Order
Citations
PageRank
Hamid Zarrabi-Zadeh111113.63
Timothy M. Chan22033150.55