Abstract
Typical behavior of the linear programming (LP) problem is studied as a relaxation of the minimum vertex cover (min-VC), 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.
- Received 28 January 2016
- Revised 13 April 2016
DOI:https://doi.org/10.1103/PhysRevE.93.053308
©2016 American Physical Society