Ground-state entropy of the random vertex-cover problem

CORC > 理论物理研究所 > 中国科学院理论物理研究所 > 理论物理所科研产出 > 理论物理所1978-2010年知识产出

	Ground-state entropy of the random vertex-cover problem
	Zhou, Jie; Zhou, Haijun; Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
刊名	PHYSICAL REVIEW E
	2009
卷号	79 期号:2 页码:-
ISSN号	1539-3755
英文摘要	Counting the number of ground states for a spin-glass or nondeterministic polynomial-complete combinatorial optimization problem is even more difficult than the already hard task of finding a single ground state. In this paper the entropy of minimum vertex covers of random graphs is estimated through a set of iterative equations based on the cavity method of statistical mechanics. During the iteration both the cavity entropy contributions and cavity magnetizations for each vertex are updated. This approach overcomes the difficulty of iterative divergence encountered in the zero-temperature first-step replica-symmetry-breaking (1RSB) spin-glass theory. It is still applicable when the 1RSB mean-field theory is no longer stable. The method can be extended to compute the entropies of ground states and metastable minimal-energy states for other random-graph spin-glass systems.
学科主题	Physics
URL标识	查看原文
WOS记录号	WOS:000263807300003
公开日期	2012-08-02
内容类型	期刊论文
源URL	[http://ir.itp.ac.cn/handle/311006/5394]
专题	理论物理研究所_理论物理所1978-2010年知识产出
通讯作者	Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Zhou, Jie,Zhou, Haijun,Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China. Ground-state entropy of the random vertex-cover problem[J]. PHYSICAL REVIEW E,2009,79(2):-.
APA	Zhou, Jie,Zhou, Haijun,&Zhou, J , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China.(2009).Ground-state entropy of the random vertex-cover problem.PHYSICAL REVIEW E,79(2),-.
MLA	Zhou, Jie,et al."Ground-state entropy of the random vertex-cover problem".PHYSICAL REVIEW E 79.2(2009):-.