Takabe Satoshi, Hukushima Koji
Graduate School of Arts and Sciences, The University of Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo 153-8902, Japan.
Phys Rev E. 2016 May;93(5):053308. doi: 10.1103/PhysRevE.93.053308. Epub 2016 May 26.
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 α=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 α≥3, 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 c=e/(α-1) where the replica symmetry is broken.
作为一种整数规划（IP）问题的最小顶点覆盖（min-VC）的松弛问题，研究了线性规划（LP）问题的典型行为。提出了一种基于α-均匀超边的厄多斯-雷尼随机图的格气模型，以在具有单参数族的通用统计力学模型中表达min-VC的LP和IP问题。统计力学分析表明，对于α = 2，在热力学极限下，LP最优解通常等于IP在临界平均度c = e以下给出的解。松弛具有良好精度的临界阈值扩展了数学结果c = 1，并且与IP的复制对称破缺阈值一致。还研究了α≥3时最小击中集、α-均匀随机图上最小顶点覆盖的LP松弛。分析和数值结果强烈表明，当复制对称被打破时，LP松弛在临界平均度c = e/(α - 1)以上无法估计最优值。
