Given a set of

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

of any online algorithm (deterministic or randomized) for Unit

Clustering is Ω(

algorithm with competitive ratio O(

Clustering of integer points. The competitive ratio of any deterministic

online algorithm for Unit Covering under L

2

Under the L

algorithm with competitive ratio O(1.321

Covering, improving on the earlier record by an exponential factor; and

give a lower bound of

algorithm for

Anirban Ghosh.)

IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria www.ist.ac.at © IST 2020