The Institute Colloquium: Hub labeling algorithms
Date
Monday, November 9, 2015 12:45 - 14:00
Speaker
Andrew V. Goldberg (Amazon.com Inc.)
Location
Raiffeisen Lecture Hall, Central Building
Series
Colloquium
Tags
Institute Colloquium
Contact
Url
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 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 results 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 developed a faster approximation algorithm; however, in pratcice it does not scale 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 complexity of computing the optimal HHL labels.