| An Improved Algorithm for Online Unit Clustering (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. We revisit the online unit clustering problem in one dimension 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 minimum 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. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||