| A randomized algorithm for online unit clustering (2006) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the onedimensional case, we show that surprisingly the naïve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||