Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems

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 $\alpha$-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 $\alpha =2$ that the LP optimal solution is typically equal to that given by the IP below the critical average degree $c=e$ in the thermodynamic limit. The critical threshold for good accuracy of the relaxation extends the mathematical result $c=1$, and coincides with the replica symmetry-breaking threshold of the IP. The LP relaxation for the minimum hitting sets with $\alpha \ge 3$, minimum vertex covers on $\alpha$-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 $c=e/(\alpha -1)$ where the replica symmetry is broken.

12 pages, 5 figures; typos are fixed

References in corpus (8)

• Message passing for vertex covers
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Clustering analysis of the ground-state structure of 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
• Phase transitions in the three-state Ising spin-glass model with finite connectivity
• 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

Cited by in corpus (4)

• Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
• Typical Approximation Performance for Maximum Coverage Problem
• Typical Performance of Approximation Algorithms for NP-hard Problems
• The Random Fractional Matching Problem