ITP OpenIR  > 理论物理所2014年知识产出
Statistical physics of hard combinatorial optimization: Vertex cover problem
Zhao, JH; Zhou, HJ; Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
2014
发表期刊CHINESE PHYSICS B
ISSN1674-1056
卷号23期号:7页码:78901
摘要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.
部门归属[Zhao Jin-Hua ; Zhou Hai-Jun] Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China
关键词Random Graphs Independence Number Cavity Method Mechanics Networks Dynamics Models Set
学科领域Physics
资助者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]
DOI10.1088/1674-1056/23/7/078901
URL查看原文
收录类别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]
WOS记录号WOS:000338925300110
引用统计
被引频次:3[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/15720
专题理论物理所2014年知识产出
通讯作者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)
暂无评论
 

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