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 language | English (US) |
---|---|
Article number | 16 |
Journal | ACM Transactions on Algorithms |
Volume | 13 |
Issue number | 1 |
DOIs | |
State | Published - Nov 2016 |
Keywords
- Distance oracles
- Labeling algorithms
ASJC Scopus subject areas
- Mathematics (miscellaneous)