Divide-and-conquer approximation algorithms via spreading metrics
Divide-and-conquer approximation algorithms via spreading metrics
复制标题
通过扩展度量的分而治之近似算法
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
B. Schieber
中科院分区：
文献类型：
--
作者：
G. Even;J. Naor;Satish Rao;B. Schieber
我们提出了一种新颖的分治范式，用于逼近 NP 难图优化问题。该范式对满足两个属性的图优化问题进行建模：首先，适用分而治之的方法。其次，分数扩展度量可以在多项式时间内计算。扩展度量将分数长度分配给输入图的边或顶点，使得优化问题不平凡的所有子图都具有大直径。此外，扩展度量提供了解决优化问题的成本的下限 /spl tau/。我们针对我们的范式建模的问题提出了一种多项式时间近似算法，其近似因子为 O (mi.
We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns fractional lengths to either edges or vertices of the input graph, such that all subgraphs on which the optimisation problem is non-trivial have large diameters. In addition, the spreading metric provides a lower bound, /spl tau/, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modelled by our paradigm whose approximation factor is O (mi.