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.
|Published in||40th International Colloquium on Automata, Languages and Programming (ICALP 2013)|