BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20160327T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20151025T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260430T094628Z
UID:5548861af187c953953135@ist.ac.at
DTSTART:20151109T124500
DTEND:20151109T140000
DESCRIPTION:Speaker: Andrew V. Goldberg\nAbstract: Given a weighted graph\,
  a distance oracle takes as an input a pair of vertices and returns the di
 stance between them. The labeling approach to distance oracle design is to
  precompute a label for every vertex so that the distances can be computed
  from the corresponding labels\, without looking at the graph. We survey r
 esults on hub labeling (HL)\, a labeling algorithm that received a lot of 
 attention recently in both theoretical and experimental contexts. HL query
  time and memory requirements depend on the label size. In polynomial time
  one can approximate the labels up to a factor of O(log(n)) [Cohen at al. 
 2003]. Our recent paper shows that the problem is NP-hard. We also develop
 ed a faster approximation algorithm\; however\, in pratcice it does not sc
 ale to large graphs. We introduce a subclass of HL\, hierarchical labels (
 HHL)\, and give experimental results showing that HHL heuristics work well
  on a wide range of problems. We also give theoretical results on the comp
 lexity of computing the optimal HHL labels.
LOCATION:Raiffeisen Lecture Hall\, Central Building\, ISTA
ORGANIZER:aeller@ist.ac.at
SUMMARY:Andrew V. Goldberg: The Institute Colloquium: Hub labeling algorith
 ms
URL:https://talks-calendar.ista.ac.at/events/553
END:VEVENT
END:VCALENDAR