Algorithms for Hub Label Optimization

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.

ICALP-BGGN-proc.pdf
PDF file

In  40th International Colloquium on Automata, Languages and Programming (ICALP 2013)

Publisher  Springer Verlag
Springer Verlag

Details

TypeInproceedings
> Publications > Algorithms for Hub Label Optimization