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.