Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective

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.

5 pages, 3 figures

References in corpus (3)

• Statistical Mechanics of the Hyper Vertex Cover 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