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
发表期刊CHINESE PHYSICS B
语种英语
关键词Random Graphs Independence Number Cavity Method Mechanics Networks Dynamics Models Set
摘要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.
2014
ISSN1674-1056
卷号23期号:7页码:78901
学科领域Physics
DOI10.1088/1674-1056/23/7/078901
收录类别SCI
项目资助者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] ; National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Natural Science Foundation of China [11121403, 11225526]
引用统计
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/15720
专题理论物理所科研产出_SCI论文
通讯作者Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
推荐引用方式
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.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Zhao, JH]的文章
[Zhou, HJ]的文章
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]的文章
百度学术
百度学术中相似的文章
[Zhao, JH]的文章
[Zhou, HJ]的文章
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]的文章
必应学术
必应学术中相似的文章
[Zhao, JH]的文章
[Zhou, HJ]的文章
[Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。