Typical Approximation Performance for Maximum Coverage Problem
arXiv:1706.08721 · doi:10.1103/PhysRevE.97.022138
Abstract
This study investigated typical performance of approximation algorithms known as belief propagation, greedy algorithm, and linear-programming relaxation for maximum coverage problems on sparse biregular random graphs. After using the cavity method for a corresponding hard-core lattice--gas model, results show 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.
arXiv comment10 pages, 6 figures
References in corpus (19)
- Random graphs with arbitrary degree distributions and their applications
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Glass models on Bethe lattices
- Core percolation on complex networks
- Core percolation in random graphs: a critical phenomena analysis
- Phase Transitions in Semidefinite Relaxations
- On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
- Message passing for vertex covers
- Statistical Mechanics of the Hyper Vertex Cover Problem
- Dynamics of heuristic optimization algorithms on random graphs
- Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
- Phase transition for cutting-plane approach to vertex-cover problem
- Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
- The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
- Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
- Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
- Typical Performance of Approximation Algorithms for NP-hard Problems
- An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
Cited by in corpus (4)
- Spin-glass model for the C-dismantling problem
- Enhancing the Performance of Quantum Neutral-Atom-Assisted Benders Decomposition
- Hybrid Quantum-Classical Multi-cut Benders Approach with a Power System Application
- Belief Propagation for Maximum Coverage on Weighted Bipartite Graph and Application to Text Summarization