Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
arXiv:1601.04273 · doi:10.1103/PhysRevE.93.053308
Abstract
Typical behavior of the linear programming (LP) problem is studied as a relaxation of the minimum vertex cover, a type of integer programming (IP) problem. A lattice-gas model on the Erdös-Rényi random graphs of -uniform hyperedges is proposed to express both the LP and IP problems of the min-VC in the common statistical-mechanical model with a one-parameter family. Statistical-mechanical analyses reveal for that the LP optimal solution is typically equal to that given by the IP below the critical average degree in the thermodynamic limit. The critical threshold for good accuracy of the relaxation extends the mathematical result , and coincides with the replica symmetry-breaking threshold of the IP. The LP relaxation for the minimum hitting sets with , minimum vertex covers on -uniform random graphs, is also studied. Analytic and numerical results strongly suggest that the LP relaxation fails to estimate optimal values above the critical average degree where the replica symmetry is broken.
arXiv comment12 pages, 5 figures; typos are fixed
References in corpus (18)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- The Bethe lattice spin glass revisited
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- The number of matchings in random graphs
- Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
- Core percolation in random graphs: a critical phenomena analysis
- Vertex cover problem studied by cavity method: Analytics and population dynamics
- Message passing for vertex covers
- Clustering analysis of the ground-state structure of the vertex-cover problem
- Statistical Mechanics of the Hyper Vertex Cover Problem
- Statistical mechanics of the multi-constraint continuous knapsack 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
- The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
- Phase transitions in the three-state Ising spin-glass model with finite connectivity
- Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
- Statistical Mechanics Analysis of the Continuous Number Partitioning Problem