ITP OpenIR  > 理论物理所科研产出  > SCI论文
Zhao, JH; Zhou, HJ; Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
Statistical physics of hard combinatorial optimization: Vertex cover problem
Source PublicationCHINESE PHYSICS B
Language英语
KeywordRandom Graphs Independence Number Cavity Method Mechanics Networks Dynamics Models Set
AbstractTypical-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.
2014
ISSN1674-1056
Volume23Issue:7Pages:78901
Subject AreaPhysics
DOI10.1088/1674-1056/23/7/078901
Indexed BySCI
Funding OrganizationNational Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Natural Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Natural Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Natural Science Foundation of China [11121403, 11225526] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Natural Science Foundation of China [11121403, 11225526]
Citation statistics
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/15720
Collection理论物理所科研产出_SCI论文
Corresponding AuthorZhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
Recommended Citation
GB/T 7714
Zhao, JH,Zhou, HJ,Zhou, HJ . Statistical physics of hard combinatorial optimization: Vertex cover problem[J]. CHINESE PHYSICS B,2014,23(7):78901.
APA Zhao, JH,Zhou, HJ,&Zhou, HJ .(2014).Statistical physics of hard combinatorial optimization: Vertex cover problem.CHINESE PHYSICS B,23(7),78901.
MLA Zhao, JH,et al."Statistical physics of hard combinatorial optimization: Vertex cover problem".CHINESE PHYSICS B 23.7(2014):78901.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhao, JH]'s Articles
[Zhou, HJ]'s Articles
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhao, JH]'s Articles
[Zhou, HJ]'s Articles
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhao, JH]'s Articles
[Zhou, HJ]'s Articles
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.