Typical Behavior of the Linear Programming Method for Combinatorial Optimization Problems: A Statistical-Mechanical Perspective

被引：8
作者：
Takabe, Satoshi [1 ]
Hukushima, Koji [1 ]
机构：
[1] Univ Tokyo, Grad Sch Arts & Sci, Meguro Ku, Tokyo 1538902, Japan
来源：
JOURNAL OF THE PHYSICAL SOCIETY OF JAPAN | 2014年 / 83卷 / 04期
关键词：
RANDOM GRAPHS; SPIN-GLASS;
D O I：
10.7566/JPSJ.83.043801
中图分类号：
O4 [物理学];
学科分类号：
0702 ;
摘要：
The typical behavior of the linear programming (LP) problem is studied as a relaxation of the minimum vertex cover problem, which is a type of integer programming (IP) problem. To deal with LP and IP using statistical mechanics, a lattice-gas model on the Erdos-Renyi random graphs is analyzed by a replica method. It is found that the LP optimal solution is typically equal to that given by IP below the critical average degree c* = e in the thermodynamic limit. The critical threshold for LP = IP extends the previous result c = 1, and coincides with the replica symmetry-breaking threshold of the IP.
引用
收藏
页数：4
相关论文
共 22 条
  • [1] [Anonymous], P 22 ANN IEEE S FDN
  • [2] [Anonymous], 1956, Linear Inequalities and Related Systems
  • [3] Core percolation in random graphs: a critical phenomena analysis
    Bauer, M
    Golinelli, O
    [J]. EUROPEAN PHYSICAL JOURNAL B, 2001, 24 (03) : 339 - 352
  • [4] Phase transition for cutting-plane approach to vertex-cover problem
    Dewenter, Timo
    Hartmann, Alexander K.
    [J]. PHYSICAL REVIEW E, 2012, 86 (04):
  • [5] Phase transitions in the three-state Ising spin-glass model with finite connectivity
    Erichsen, R., Jr.
    Theumann, W. K.
    [J]. PHYSICAL REVIEW E, 2011, 83 (06):
  • [6] Exact solutions for diluted spin glasses and optimization problems
    Franz, S
    Leone, M
    Ricci-Tersenghi, F
    Zecchina, R
    [J]. PHYSICAL REVIEW LETTERS, 2001, 87 (12) : 127209 - 127209
  • [7] GEYER CJ, 1991, COMPUTING SCIENCE AND STATISTICS, P156
  • [8] Exchange Monte Carlo method and application to spin glass simulations
    Hukushima, K
    Nemoto, K
    [J]. JOURNAL OF THE PHYSICAL SOCIETY OF JAPAN, 1996, 65 (06) : 1604 - 1608
  • [9] Statistical mechanics of the multi-constraint continuous knapsack problem
    Inoue, J
    [J]. JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1997, 30 (04): : 1047 - 1058
  • [10] Khachiyan Leonid G, 1980, USSR Comput. Math. Math. Phys., V20, P53, DOI [DOI 10.1016/0041-5553(80)90061-0, 10.1016/0041-5553(80)90061-0]
123