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:20260405T215827Z
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\, ISTA
ORGANIZER:hwagner@ist.ac.at
SUMMARY:Csaba Toth: GeomTop Seminar: Online Unit Clustering and Covering in
  Euclidean Space
URL:https://talks-calendar.ista.ac.at/events/1994
END:VEVENT
END:VCALENDAR