BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20190331T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20191027T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20190717T150555Z
UID:5c8a5b8a66ff2609326646@ist.ac.at
DTSTART:20190529T130000
DTEND:20190529T141500
DESCRIPTION:Speaker: Csaba Toth\nhosted by Uli Wagner\nAbstract: Given a se
t of n points in a metric space\, that arrive one by one\, the Unit Cluste
ring problem consists of partitioning the points into the minimum number o
f clusters (subsets) of diameter at most one\; while the Unit Covering pro
blem consists of covering all points by the minimum number of balls of uni
t radius. In this talk\, we explore how the competitive ratio of online al
gorithms 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 on
line algorithm with competitive ratio O(d2) for Unit Clustering of integer
points. The competitive ratio of any deterministic online algorithm for U
nit Covering under L∞ is at least 2d\; and this ratio is the best possib
le.Under the L2 norm\, we describe an online deterministic algorithm with
competitive ratio O(1.321d) for Unit Covering\, improving on the earlier r
ecord by an exponential factor\; and give a lower bound of d+1 for the com
petitive ratio of any algorithm for d&geq\;1 (Joint work with Adrian Dumit
rescu and Anirban Ghosh.)
LOCATION:Mondi Seminar Room 3\, Central Building\, IST Austria
ORGANIZER:hwagner@ist.ac.at
SUMMARY:GeomTop Seminar: Online Unit Clustering and Covering in Euclidean S
pace
URL:https://talks-calendar.app.ist.ac.at/events/1994
END:VEVENT
END:VCALENDAR