Algorithms for Hub Label Optimization
- Maxim Babenko ,
- Andrew Goldberg ,
- Anupam Gupta ,
- Viswanath Nagarajan
40th International Colloquium on Automata, Languages and Programming (ICALP 2013) |
Published by Springer Verlag
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.