Typical Performance of Approximation Algorithms for NP-hard Problems
arXiv:1605.04679 · doi:10.1088/1742-5468/2016/11/113401
Abstract
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 some theoretical frameworks. Here three approximation algorithms are examined; the linear-programming relaxation, the loopy-belief propagation, and the leaf-removal algorithm. The former two algorithms are analyzed using the statistical-mechanical technique while the average-case analysis of the last one is studied by the generating function method. These algorithms have a threshold in the typical performance with increasing the 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. We provide some conditions for classifying the graph ensembles and demonstrate explicitly examples for the difference in the threshold.
arXiv comment21 pages, 5 figures; typos are fixed
References in corpus (20)
- Emergence of scaling in random networks
- Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- The number of matchings in random graphs
- Random incidence matrices: moments of the spectral density
- Phase Transitions in Semidefinite Relaxations
- Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
- Message passing for vertex covers
- Computational complexity arising from degree correlations in networks
- Statistical Mechanics of the Minimum Dominating Set Problem
- The hard-core model on random graphs revisited
- Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
- Statistical physics of hard combinatorial optimization: The vertex cover problem
- 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
- 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
- Tightness of LP via Max-product Belief Propagation
- Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems