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:
Institute colloquium
Contact:
ELLER Arinya
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.