Algorithms for Hub Label Optimization
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 (l∞-norm) and simultaneously minimizing a constant number of lp-norms. Prior to this, an O(log n)- approximation algorithm was known [Cohen et al. 2003] only for minimizing the total label size (l1-norm).