Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
arXiv:1309.6925 · doi:10.7566/JPSJ.83.043801
Abstract
Typical behavior of the linear programming problem (LP) is studied as a relaxation of the minimum vertex cover problem, which is a type of the integer programming problem (IP). To deal with the LP and IP by statistical mechanics, a lattice-gas model on the Erdös-Rényi random graphs is analyzed by a replica method. It is found that the LP optimal solution is typically equal to that of the IP below the critical average degree c*=e in the thermodynamic limit. The critical threshold for LP=IP is beyond a mathematical result, c=1, and coincides with the replica-symmetry-breaking threshold of the IP.
arXiv comment5 pages, 3 figures
References in corpus (9)
- 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
- Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
- Core percolation in random graphs: a critical phenomena analysis
- Exact solutions for diluted spin glasses and optimization problems
- Statistical Mechanics of the Hyper Vertex Cover Problem
- Statistical mechanics of the multi-constraint continuous knapsack problem
- Phase transition for cutting-plane approach to vertex-cover problem
- Phase transitions in the three-state Ising spin-glass model with finite connectivity
Cited by in corpus (8)
- Drawing Phase Diagrams of Random Quantum Systems by Deep Learning the Wave Functions
- Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
- Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
- Typical Approximation Performance for Maximum Coverage Problem
- Typical Performance of Approximation Algorithms for NP-hard Problems
- Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
- An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
- Constructing Concrete Hard Instances of the Maximum Independent Set Problem