[Colloquium] REMINDER: Talks at TTIC: Andrew V. Goldberg

[Dawn Ellis]

When:     Friday, November 7th at 11am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Andrew V. Goldberg

Title:       The Hub Labeling Algorithm

Abstract:

Given a weighted graph, a distance oracle takes as an input a pair of
vertices and returns the distance between them. The labeling approach to
distance oracles 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 results on hub labeling (HL), a labeling algorithm
that received a lot of attention recently.

HL query time and memory requirements depend on the label size. While some
graphs admit small labels, one can prove that there are graphs for which
the labels must be large. Computing optimal hub labels is hard, but in
polynomial time one can approximate them up to a factor of O(log(n)) [Cohen
at al. 2003]. This can be done for the total label size and the maximum
label size [Babenko et al. 2013].

Hierarchical labels (HHL) are a special class of HL. HHL labels appear to
be more practical than general HL labels, although in theory they can be
significantly larger. HHL heuristics lead to the fastest implementations of
distance oracles for road networks and for some social and computer
networks.

We give experimental results showing that HHL heuristics can be very
effective, show that known algorithms have theoretical limitations, and
motivate the problem of designing a theoretically justified HHL algorithm.

BIO:  http://research.microsoft.com/en-us/people/goldberg/

Host:  Alexander Razborov,  razborov at ttic.edu

-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20141106/44b5ca16/attachment.htm