Approximating a finite metric by a small number of tree metrics Export

@inproceedings{citeulike:2967054, abstract = {Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution \μ on them such that the expected stretch of any edge of G in a tree chosen according to \μ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming}, author = {Charikar, M. and Chekuri, C. and Goel, A. and Guha, S. and Plotkin, S.}, booktitle = {Foundations of Computer Science, 1998. Proceedings.39th Annual Symposium on}, citeulike-article-id = {2967054}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/SFCS.1998.743488}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=743488}, doi = {10.1109/SFCS.1998.743488}, journal = {Foundations of Computer Science, 1998. Proceedings.39th Annual Symposium on}, keywords = {approximation, metric\_embeddings}, pages = {379--388}, posted-at = {2008-11-29 17:32:14}, priority = {2}, title = {Approximating a finite metric by a small number of tree metrics}, url = {http://dx.doi.org/10.1109/SFCS.1998.743488}, year = {1998} }

TY - CONF ID - citeulike:2967054 L3 - citeulike-article-id:2967054 N2 - Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution μ on them such that the expected stretch of any edge of G in a tree chosen according to μ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming JF - Foundations of Computer Science, 1998. Proceedings.39th Annual Symposium on EP - 388 TI - Approximating a finite metric by a small number of tree metrics T2 - Foundations of Computer Science, 1998. Proceedings.39th Annual Symposium on SP - 379 KW - approximation KW - metric_embeddings AU - Charikar, M AU - Chekuri, C AU - Goel, A AU - Guha, S AU - Plotkin, S PY - 1998/// UR - http://dx.doi.org/10.1109/SFCS.1998.743488 ER -