Statistical physics of hard combinatorial optimization：Vertex cover problem

doi:10.1088/1674-1056/23/7/078901

中国物理B ›› 2014, Vol. 23 ›› Issue (7): 78901-078901.doi: 10.1088/1674-1056/23/7/078901

所属专题： TOPICAL REVIEW — Statistical Physics and Complex Systems

• TOPICAL REVIEW—Statistical Physics and Complex Systems • 上一篇下一篇

Statistical physics of hard combinatorial optimization：Vertex cover problem

赵金华, 周海军

State Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China

收稿日期:2014-03-20 修回日期:2014-05-22 出版日期:2014-07-15 发布日期:2014-07-15
基金资助:
Project supported by the National Basic Research Program of China (Grant No. 2013CB932804), the Knowledge Innovation Program of Chinese Academy of Sciences (Grant No. KJCX2-EW-J02), and the National Natural Science Foundation of China (Grant Nos. 11121403 and 11225526).

Statistical physics of hard combinatorial optimization：Vertex cover problem

Zhao Jin-Hua (赵金华), Zhou Hai-Jun (周海军)

State Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China

Received:2014-03-20 Revised:2014-05-22 Online:2014-07-15 Published:2014-07-15
Contact: Zhou Hai-Jun E-mail:zhouhj@itp.ac.cn
About author:89.20.Ff; 75.10.Nr; 02.10.Ox; 05.10.–a
Supported by:
Project supported by the National Basic Research Program of China (Grant No. 2013CB932804), the Knowledge Innovation Program of Chinese Academy of Sciences (Grant No. KJCX2-EW-J02), and the National Natural Science Foundation of China (Grant Nos. 11121403 and 11225526).

摘要/Abstract

摘要： Typical-case computation complexity is a research topic at the boundary of computer science, applied mathematics, and statistical physics. In the last twenty years, the replica-symmetry-breaking mean field theory of spin glasses and the associated message-passing algorithms have greatly deepened our understanding of typical-case computation complexity. In this paper, we use the vertex cover problem, a basic nondeterministic-polynomial (NP)-complete combinatorial optimization problem of wide application, as an example to introduce the statistical physical methods and algorithms. We do not go into the technical details but emphasize mainly the intuitive physical meanings of the message-passing equations. A nonfamiliar reader shall be able to understand to a large extent the physics behind the mean field approaches and to adjust the mean field methods in solving other optimization problems.

关键词: spin glass, energy minimization, replica symmetry breaking, belief propagation

Abstract: Typical-case computation complexity is a research topic at the boundary of computer science, applied mathematics, and statistical physics. In the last twenty years, the replica-symmetry-breaking mean field theory of spin glasses and the associated message-passing algorithms have greatly deepened our understanding of typical-case computation complexity. In this paper, we use the vertex cover problem, a basic nondeterministic-polynomial (NP)-complete combinatorial optimization problem of wide application, as an example to introduce the statistical physical methods and algorithms. We do not go into the technical details but emphasize mainly the intuitive physical meanings of the message-passing equations. A nonfamiliar reader shall be able to understand to a large extent the physics behind the mean field approaches and to adjust the mean field methods in solving other optimization problems.

Key words: spin glass, energy minimization, replica symmetry breaking, belief propagation

中图分类号: (Computer science and technology)

89.20.Ff

75.10.Nr (Spin-glass and other random models) 02.10.Ox (Combinatorics; graph theory)

赵金华, 周海军. Statistical physics of hard combinatorial optimization：Vertex cover problem[J]. 中国物理B, 2014, 23(7): 78901-078901.

Zhao Jin-Hua (赵金华), Zhou Hai-Jun (周海军). Statistical physics of hard combinatorial optimization：Vertex cover problem[J]. Chin. Phys. B, 2014, 23(7): 78901-078901.

参考文献 76

[1]	Cook S A 1971 Proceedings of the 3rd Annual ACM Symposium on Theory of Computing edited by Lewis P M, Fischer M J, Hopcroft J E, Rosenberg A L, Thatcher J W and Young P R (New York) p. 151
[2]	Karp R M 1972 Complexity of Computer Computations (New York: Plenum Press) p. 85
[3]	Garey Mand Johnson D S 1979 Computers and Intractability: A Guide to the Theory of NP-Completeness (San Francisco: Freeman)
[4]	Papadimitriou C and Steiglitz K 1998 Combinatorial Optimization: Algorithms and Complexity (New York: Dover)
[5]	Cheeseman P, Kanefsky B and Taylor W 1991 Proceedings 12th Int. Joint Conf. on Artificial Intelligence (Sydney) p. 163
[6]	Mézard M, Parisi G and Virasoro M A 1987 Spin Glass Theory and Beyond (Singapore: World Scientific)
[7]	Nishimori H 2001 Statistical Physics of Spin Glasses and Information Processing (Oxford: Oxford University Press)
[8]	Mézard M and Montanari A 2009 Information, Physics, and Computation (New York: Oxford Unversity Press)
[9]	Talagrand M 2003 Spin Glasses (Berlin: Springer)
[10]	Hartmann A K and Weigt M 2005 Phase Transitions in Combinatorial Optimization Problems (Weinhei: Wiley-VCH)
[11]	Mézard M and Parisi G 2001 Eur. Phys. J. B 20 217
[12]	Mézard M and Parisi G 2003 J. Stat. Phys. 111 1
[13]	Mézard M and Parisi G 1986 J. Physique 47 1285
[14]	Monasson R and Zecchina R 1997 Phys. Rev. E 56 1357
[15]	Mézard M, Parisi G and Zecchina R 2002 Science 297 812
[16]	Mézard M and Zecchina R 2002 Phys. Rev. E 66 056126
[17]	Montanari A, Ricci-Tersenghi F and Semerjian G 2008 J. Stat. Mech.: Theor. Exp. P04004
[18]	Krzakala F, Montanari A, Ricci-Tersenghi F, Semerjian G and Zdeborová L 2007 Proc. Natl. Acad. Sci. USA 104 10318
[19]	Franz S, Leone M, Ricci-Tersenghi F and Zecchina R 2001 Phys. Rev. Lett. 87 127209
[20]	Cocco S, Dubois O, Mandler J and Monasson R 2003 Phys. Rev. Lett. 90 047205
[21]	Mézard M, Ricci-Tersenghi F and Zecchina R 2003 J. Stat. Phys. 111 505
[22]	Weigt M and Hartmann A K 2000 Phys. Rev. Lett. 84 6118
[23]	Weigt M and Hartmann A K 2001 Phys. Rev. Lett. 86 1658
[24]	Weigt M and Hartmann A K 2001 Phys. Rev. E 63 056127
[25]	Hartmann A K and Weigt M 2003 J. Phys. A: Math. Gen. 36 11069
[26]	Zhou H J 2003 Eur. Phys. J. B 32 265
[27]	Weigt M and Zhou H J 2006 Phys. Rev. E 74 046110
[28]	Zhou J and Zhou H J 2009 Phys. Rev. E 79 020103
[29]	Zhang P, Zeng Y and Zhou H J 2009 Phys. Rev. E 80 021122
[30]	Dall’Asta L, Pin P and Ramezanpour A 2009 Phys. Rev. E 80 061136
[31]	Mézard M and Tarzia M 2007 Phys. Rev. E 76 041124
[32]	Mézard M, Tarzia M and Toninelli C 2008 J. Phys. C: Conf. Ser. 95 012019
[33]	van Mourik J and Saad D 2002 Phys. Rev. E 66 056120
[34]	Mulet R, Pagnani A, Weigt M and Zecchina R 2002 Phys. Rev. Lett. 89 268701
[35]	Zdeborová L and Krzakala F 2007 Phys. Rev. E 76 031131
[36]	Karp R M and Sipser M 1981 Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (NJ: Wiley-IEEE Computer Society Press) p. 364
[37]	Zhou H J and Ou-Yang Z C 2003 arXiv:0309348v1 [cond-mat]
[38]	Zdeborová L and Mézard M 2006 J. Stat. Mech.: Theor. Exp. P05003
[39]	Zhou H J 2013 Eur. Phys. J. B 86 455
[40]	Breitbart Y, Chan C, Garofalakis M, Rastogi R and Silberschatz A 2001 Proceedings of IEEE INFOCOM' 2001 (Anchorage) p. 933
[41]	Park K and Lee H 2001 Proceedings ACM SIGCOM 2001 (San Diego)
[42]	Gomez-Gardenes J, Echenique P and Moreno Y 2006 Eur. Phys. J. B 49 259
[43]	Huang H, Raymond J and Wong K Y M 2014 J. Stat. Phys. (in press) (2012 arXiv:1209.4134 [cond-mat.dis-nn])
[44]	Harant J 1998 Discr. Math. 188 239
[45]	Caro C 1979 Technical Reports (Tel-Aviv University)
[46]	Wei V K 1981 Techinical Reports 81-11217-9 (Bell Laboratories NJ)
[47]	Harant J 2011 Disc. Appl. Math. 159 966
[48]	Harant J 2006 Discussiones Mathematicae Graph Theory 26 431
[49]	Angel E, Campigotto R and Laforest C 2013 Disc. Appl. Math. 161 847
[50]	Bollobás B 2001 Random Graphs (2nd edn.) (Cambridge: Cambridge University Press)
[51]	Erdös P and Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[52]	Gazmuri P G 1984 Network 14 367
[53]	Dani V and Moore C 2011 Lect. Notes Comput. Sci. 6845 472
[54]	Frieze A M 1990 Discr. Math. 81 171
[55]	Bauer M and Golinelli O 2001 Eur. Phys. J. B 24 339
[56]	Newman M E J and Barkema G T 1999 Monte Carlo Methods in Statistical Physics (USA: Oxford University Press)
[57]	Landau D and Binder K 2013 A Guide to Monte Carlo Simulations in Statistical Physics (3rd edn.) (Cambridge: Cambrige University Press)
[58]	Bathel W and Hartmann A K 2004 Phys. Rev. E 70 066120
[59]	Marinari K and Paris G 1992 Europhys. Lett. 19 45
[60]	Hukushima K and Nemoto K 1996 J. Phys. Soc. Jpn. 65 1604
[61]	Zhou H J 2005 Phys. Rev. Lett. 94 217203
[62]	Zhou H J 2012 Phys. Rev. Lett. 109 199901
[63]	Liu Y Y, Csóka E, Zhou H J and Pósfai M 2012 Phys. Rev. Lett. 109 205703
[64]	Zhou H J 2014 Spin Glasses and Message Passing (in preparation)
[65]	Wei W, Zhang R, Guo B and Zhang Z 2012 Phys. Rev. E 86 016112
[66]	Binder K and Young A P 1986 Rev. Mod. Phys. 58 801
[67]	Bethe H A 1935 Proc. R. Soc. London A 150 552
[68]	Peierls R 1936 Proc. R. Soc. London A 154 207
[69]	Peierls R 1936 Proc. Camb. Phil. Soc. 32 477
[70]	Xiao J Q and Zhou H J 2011 J. Phys. A: Math. Theor. 44 425001
[71]	Zhou H J and Wang C 2012 J. Stat. Phys. 148 513
[72]	Bramoullé Y and Kranton R 2007 J. Econ. Theory 135 478
[73]	Galeotti A, Goyal S, Jackson M, Vega-Redondo F and Yariv L 2010 Rev. Econ. Stud. 77 218
[74]	Ritort F and Sollich P 2003 Add. Phys. 52 219
[75]	Brešar B, Kardoš F, Katrenič J and Semanišin G 2011 Disc. Appl. Math. 159 1189
[76]	Novotný M 2010 Lect. Notes Comput. Sci. 6033 106

Statistical physics of hard combinatorial optimization：Vertex cover problem

Statistical physics of hard combinatorial optimization：Vertex cover problem

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 76

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Dan-Dan Yan(颜丹丹), Xing-Kui Fan(范兴奎), Zhen-Yu Chen(陈祯羽), and Hong-Yang Ma(马鸿洋). Low-loss belief propagation decoder with Tanner graph in quantum error-correction codes[J]. 中国物理B, 2022, 31(1): 10304-010304.
[2]	Long Tian(田龙), Panpan Liu(刘盼盼), Tao Hong(洪涛), Tilo Seydel, Xingye Lu(鲁兴业), Huiqian Luo(罗会仟), Shiliang Li(李世亮), and Pengcheng Dai(戴鹏程). Excess-iron driven spin glass phase in Fe_1+yTe_1-xSe_x[J]. 中国物理B, 2021, 30(8): 87402-087402.
[3]	Lei Duan(段磊), Xian-Cheng Wang(望贤成), Jun Zhang(张俊), Jian-Fa Zhao(赵建发), Wen-Min Li(李文敏), Li-Peng Cao(曹立朋), Zhi-Wei Zhao(赵志伟), Changjiang Xiao(肖长江), Ying Ren(任瑛), Shun Wang(王顺), Jinlong Zhu(朱金龙), and Chang-Qing Jin(靳常青). Doping effect on the structure and physical properties of quasi-one-dimensional compounds Ba₉Co₃(Se_1-xS_x)₁₅ (x = 0-0.2)[J]. 中国物理B, 2021, 30(10): 106101-106101.
[4]	段磊, 望贤成, 张俊, 赵建发, 曹立朋, 李文敏, 于润泽, 邓正, 靳常青. Synthesis, structure, and properties of Ba₉Co₃Se₁₅ with one-dimensional spin chains[J]. 中国物理B, 2020, 29(3): 36102-036102.
[5]	刘宇轩, 刘哲宏, 叶旭斌, 申旭东, 王潇, 周博文, 周光辉, 龙有文. Spin glassy behavior and large exchange bias effect in cubic perovskite Ba_0.8Sr_0.2FeO_3-δ[J]. 中国物理B, 2019, 28(6): 68104-068104.
[6]	马祯, 冉柯静, 王靖珲, 鲍嵩, 蔡正蔚, 李世超, 温锦生. Recent progress on magnetic-field studies on quantum-spin-liquid candidates[J]. 中国物理B, 2018, 27(10): 106101-106101.
[7]	赖大荣, 舒欣. Link prediction in complex networks via modularity-based belief propagation[J]. 中国物理B, 2017, 26(3): 38902-038902.
[8]	Erhan Albayrak. Magnetic phase diagrams of Fe-Mn-Al alloy on the Bethe lattice[J]. 中国物理B, 2017, 26(2): 20502-020502.
[9]	吕益飞, 向建勇, 温福昇, 吕伟明, 胡文涛, 柳忠元. Double spin-glass-like behavior and antiferromagnetic superexchange interaction between Fe³⁺ ions in α-Ga_2-xFe_xO₃ (0 ≤ x ≤ 0.4)[J]. 中国物理B, 2015, 24(3): 37502-037502.
[10]	代佳, 周萍, 王朋帅, 庞斐, Tim J. Munsie, Graeme M. Luke, 张金珊, 于伟强. Spin frustration and magnetic ordering in triangular lattice antiferromagnet Ca₃CoNb₂O₉[J]. 中国物理B, 2015, 24(12): 127508-127508.
[11]	陈红, 杨旭, 张培松, 梁磊, 洪源泽, 魏英进, 陈岗, 杜菲, 王春忠. Observation of spin glass transition in spinel LiCoMnO₄[J]. 中国物理B, 2015, 24(12): 127501-127501.
[12]	芮文彬, 何茂诚, 游彪, 时钟, 周仕明, 肖明文, 高远, 张维, 孙力, 杜军. Asymmetric exchange bias training effect in spin glass (FeAu)/FeNi bilayers[J]. 中国物理B, 2014, 23(10): 107502-107502.
[13]	M Y Ali, J Poulter. Spin-correlation function of the fully frustrated Ising model and ± J Ising spin glass on the square lattice[J]. 中国物理B, 2013, 22(6): 67502-067502.
[14]	段寒凝, 袁松柳, 郑先锋, 田召明 . The synthesis and exchange bias effect of monodisperse NiO nanocrystals[J]. 中国物理B, 2012, 21(7): 78101-078101.
[15]	张开成, 宋朋云. Spin glass dynamics in RKKY interacting disordered magnetic system[J]. 中国物理B, 2010, 19(9): 97105-097105.