Algorithms for hub label optimization

Maxim Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the hub label optimization problem, which arises in designing fast preprocessing-based shortest-path algorithms. We give O(log n)-approximation algorithms for the objectives of minimizing the maximum label size (ℓ-norm) and simultaneously minimizing a constant number of ℓp-norms. Prior to this, an O(log n)-approximation algorithm was known [Cohen et al. 2003] only for minimizing the total label size (ℓ1-norm).

Original languageEnglish (US)
Article number16
JournalACM Transactions on Algorithms
Volume13
Issue number1
DOIs
StatePublished - Nov 2016

Keywords

  • Distance oracles
  • Labeling algorithms

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Algorithms for hub label optimization'. Together they form a unique fingerprint.

Cite this