• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Algorithms for Hub Label Optimization

ACM Transactions on Algorithms. 2016. Vol. 13. No. 1. P. 16:1-16:17.
Babenko M. A., Goldberg A., Gupta A., Nagarajan V.

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).