Name
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 one-dimensional 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. |
Year | DOI | Venue |
|---|---|---|
2006 | https://doi.org/10.1007/s00224-007-9085-7 | Theory of Computing Systems |
Keywords | Field | DocType |
Online algorithms,Randomized algorithms,Unit clustering | Randomized algorithm,Online algorithm,Discrete mathematics,Combinatorics,Interval graph,Upper and lower bounds,Partition (number theory),Cluster analysis,Mathematics,Unit sphere,Competitive analysis | Conference |
Volume | Issue | ISSN |
45 | 3 | 1432-4350 |
ISBN | Citations | PageRank |
3-540-69513-3 | 9 | 0.71 |
References | Authors | |
19 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Timothy M. Chan | 1 | 2033 | 150.55 |
| Hamid Zarrabi-Zadeh | 2 | 111 | 13.63 |