Algorithms for Hub Label Optimization

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

Abstract

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.

Details

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