论文标题
对图中最小统治设置的某些近似算法的性能研究
A performance study of some approximation algorithms for minimum dominating set in a graph
论文作者
论文摘要
我们实现并测试了几种近似算法的性能，以计算图形的最小主导集。这些算法是标准的贪婪算法，最近的LP圆形算法和我们通过组合贪婪和LP圆形圆形算法设计的混合算法。所有算法在其理论分析中的表现都比预期的要好，并且具有较小的性能比，衡量的是输出的大小除以LP物镜下限。但是，每个人都可能比其他优势。例如，LP四舍五入算法通常优于稀疏现实世界图上的其他算法。在具有400,000多个顶点的图表上，LP圆形花费了不到15秒的CPU时间来生成具有性能比1.011的解决方案，而贪婪和混合算法在相似的时间内生成了性能比1.12的解决方案。对于合成图，混合算法通常优于其他算法，而对于超管和k-queens图，贪婪的表现优于其余的。混合算法的另一个优点是解决LP求解器崩溃的非常大问题，如在770万+顶点的真实图表上所示。
We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm, the recent LP rounding algorithms and a hybrid algorithm that we design by combining the greedy and LP rounding algorithms. All algorithms perform better than anticipated in their theoretical analysis, and have small performance ratios, measured as the size of output divided by the LP objective lower-bound. However, each may have advantages over the others. For instance, LP rounding algorithm normally outperforms the other algorithms on sparse real-world graphs. On a graph with 400,000+ vertices, LP rounding took less than 15 seconds of CPU time to generate a solution with performance ratio 1.011, while the greedy and hybrid algorithms generated solutions of performance ratio 1.12 in similar time. For synthetic graphs, the hybrid algorithm normally outperforms the others, whereas for hypercubes and k-Queens graphs, greedy outperforms the rest. Another advantage of the hybrid algorithm is to solve very large problems where LP solvers crash, as demonstrated on a real-world graph with 7.7 million+ vertices.
