GeomTop Seminar: Online Unit Clustering and Covering in Euclidean Space
Date
Wednesday, May 29, 2019 13:00 - 14:15
Speaker
Csaba Toth (California State University Northridge)
Location
Mondi Seminar Room 3, Central Building
Series
Seminar/Talk
Tags
Mathematics and CS Seminar, mathematical_seminar_ics
Host
Uli Wagner
Contact
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.)