Given a set of n points in a metric space, that arrive one by one, the Unit Clustering problem consists of partitioning the points into the minimum number of clusters (subsets) of diameter at most one; while the Unit Covering problem consists of covering all points by the minimum number of balls of unit radius. In this talk, we explore how the competitive ratio of online algorithms depend on the dimension in Euclidean spaces.
Under the L∞ norm, we show that the competitive ratio of any online algorithm (deterministic or randomized) for Unit Clustering is Ω(d). We also give a randomized online algorithm with competitive ratio O(d2) for Unit Clustering of integer points. The competitive ratio of any deterministic online algorithm for Unit Covering under L∞ is at least 2d; and this ratio is the best possible.
Under the L2 norm, we describe an online deterministic algorithm with competitive ratio O(1.321d) for Unit Covering, improving on the earlier record by an exponential factor; and give a lower bound of d+1 for the competitive ratio of any algorithm for d≥1 (Joint work with Adrian Dumitrescu and Anirban Ghosh.)