Typical approximation performance for maximum coverage problem
Typical approximation performance for maximum coverage problem
复制标题
最大覆盖问题的典型近似性能
DOI：
10.1103/physreve.97.022138
复制
发表时间：
2018
影响因子：
2.4
通讯作者：
Hukushima Koji
中科院分区：
文献类型：
--
作者：
Takabe Satoshi;Maehara Takanori;Hukushima Koji
本研究探讨了稀疏双正则随机图中最大覆盖问题的近似算法，如信念传播，贪婪算法和线性规划松弛的典型性能。我们对相应的硬核格子气模型使用腔方法后，结果表明，在典型的信念传播性能阈值中存在两个不同的复制对称性阈值及其破缺阈值。在低密度区域，通过理论分析得出了三种算法在典型性能阈值下的优越性。虽然贪婪算法和线性规划松弛算法在最坏情况下的逼近比相同，但它们的典型性能阈值不同，表明典型性能的重要性。数值模拟的结果验证了理论分析，并暗示了进一步的相互关系的近似算法。
This study investigated the typical performance of approximation algorithms known as belief propagation, the greedy algorithm, and linear-programming relaxation for maximum coverage problems in sparse biregular random graphs. After we used the cavity method for a corresponding hard-core lattice-gas model, results showed that two distinct thresholds of replica-symmetry and its breaking exist in the typical performance threshold of belief propagation. In the low-density region, the superiority of three algorithms in terms of a typical performance threshold is obtained by some theoretical analyses. Although the greedy algorithm and linear-programming relaxation have the same approximation ratio in worst-case performance, their typical performance thresholds are mutually different, indicating the importance of typical performance. Results of numerical simulations validate the theoretical analyses and imply further mutual relations of approximation algorithms.