Approximating a finite metric by a small number of tree metrics
Approximating a finite metric by a small number of tree metrics
复制标题
通过少量的树度量来近似有限度量
DOI：
10.1109/sfcs.1998.743488
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Serge A. Plotkin
中科院分区：
文献类型：
--
作者：
M. Charikar;C. Chekuri;Ashish Goel;S. Guha;Serge A. Plotkin
Y.Bartal(1996,1998)给出了一个随机多项式时间算法，该算法给定任意n点度量G，构造一棵树T，使得任意边的期望伸展(变形)至多为O(Lognloglogn)。他的结果已经发现了几个应用，特别是导致了许多图优化问题的近似算法。然而，基于他的结果的近似算法本质上是随机化的。本文对Bartal算法在逼近算法设计中的应用进行了随机化处理。我们给出了一个有效的多项式时间算法，在给定有限的n点度量G的情况下，构造O(Nlogn)树和它们上的概率分布/splu/，使得根据/splu/选择的树中G的任意边的期望伸展至多为O(Lognlogn).我们的结果证明有限的度量可以用少量的树度量来概率地近似。我们得到了用于批量购买网络设计和车辆路径的第一个确定性近似算法；此外，我们还包含了我们先前关于去随机化的工作的结果。我们的主要结果是通过线性规划将度量空间的概率逼近作为确定性优化问题的一种新的观点得到的。
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 /spl mu/ on them such that the expected stretch of any edge of G in a tree chosen according to /spl mu/ 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.