Upcoming Talks

Ist logo

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: Mathematics and CS Seminar
Host: Uli Wagner
Contact: WAGNER Hubert

Abstract:

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.)
Qr image
Download ICS Download invitation
Back to eventlist