Statistical physics of hard combinatorial optimization: Vertex cover problem
文献类型：期刊论文
| 作者 | Zhou, HJ
|
| 刊名 | CHINESE PHYSICS B
 |
| 出版日期 | 2014 |
| 卷号 | 23期号:7页码:78901 |
| 关键词 | RANDOM GRAPHS INDEPENDENCE NUMBER CAVITY METHOD MECHANICS NETWORKS DYNAMICS MODELS SET |
| ISSN号 | 1674-1056 |
| 通讯作者 | Zhou, HJ (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China. |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| 收录类别 | SCI |
| 资助信息 | National Basic Research Program of China [2013CB932804]; Chinese Academy of Sciences [KJCX2-EW-J02]; National Natural Science Foundation of China [11121403, 11225526] |
| 原文出处 | http://dx.doi.org/10.1088/1674-1056/23/7/078901 |
| 语种 | 英语 |
| WOS记录号 | WOS:000338925300110 |
| 公开日期 | 2015-06-03 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/15720]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 推荐引用方式 GB/T 7714 | Zhou, HJ. Statistical physics of hard combinatorial optimization: Vertex cover problem[J]. CHINESE PHYSICS B,2014,23(7):78901. |
| APA | Zhou, HJ.(2014).Statistical physics of hard combinatorial optimization: Vertex cover problem.CHINESE PHYSICS B,23(7),78901. |
| MLA | Zhou, HJ."Statistical physics of hard combinatorial optimization: Vertex cover problem".CHINESE PHYSICS B 23.7(2014):78901. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。