Typical performance of approximation algorithms for NP-hard problems
Typical performance of approximation algorithms for NP-hard problems
复制标题
DOI：
10.1088/1742-5468/2016/11/113401
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Satoshi Takabe;K. Hukushima
中科院分区：
文献类型：
--
作者：
Satoshi Takabe;K. Hukushima
研究了随机最小顶点覆盖问题近似算法的典型性能。讨论了一类具有任意度分布的随机图系综，给出了一个理论框架。在这里，三个近似算法进行检查：线性规划松弛，循环信念传播，和叶去除算法。前两种算法的分析使用的是一个物理力学技术，而平均情况下的分析，最后一个是使用生成函数的方法进行。这些算法的典型性能随着随机图的平均度的增加而具有阈值，低于该阈值，它们以高概率找到真正的最优解。我们的研究表明，只有三种情况下，由典型的性能阈值的顺序确定。此外，我们提供了一些分类的图集成的条件，并明确地证明了一些例子的阈值的差异。
Typical performance of approximation algorithms is studied for randomized minimum vertex cover problems. A wide class of random graph ensembles characterized by an arbitrary degree distribution is discussed with the presentation of a theoretical framework. Herein, three approximation algorithms are examined: linear-programming relaxation, loopy-belief propagation, and the leaf-removal algorithm. The former two algorithms are analyzed using a statistical–mechanical technique, whereas the average-case analysis of the last one is conducted using the generating function method. These algorithms have a threshold in the typical performance with increasing average degree of the random graph, below which they find true optimal solutions with high probability. Our study reveals that there exist only three cases, determined by the order of the typical performance thresholds. In addition, we provide some conditions for classification of the graph ensembles and demonstrate explicitly some examples for the difference in thresholds.