Algorithms for Hub Label Optimization
Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan · ACM Transactions on Algorithms · 2016
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).