Algorithms for Hub Label Optimization

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


Cohen et al. developed an O(log n)-approximation algorithm for minimizing the total hub label size (L1 norm). We give O(log n)-approximation algorithms for the problems of minimizing the maximum label (infinity norm), any Lp norm, and minimizing Lp and Lq norms simultaneously.


Publication typeInproceedings
Published in40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
PublisherSpringer Verlag
> Publications > Algorithms for Hub Label Optimization