Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process

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

	Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
	Zhou, HJ
刊名	PHYSICAL REVIEW E
	2011
卷号	83 期号:5 页码:52101
关键词	CONSTRAINT SATISFACTION PROBLEMS SATISFIABILITY PROBLEMS CAVITY METHOD OPTIMIZATION
ISSN号	1539-3755
通讯作者	Ma, H (reprint author), Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China.
英文摘要	In this brief report we explore the energy landscapes of two spin glass models using a greedy single-spin flipping process, Gmax. The ground-state energy density of the random maximum two-satisfiability problem is efficiently approached by Gmax. The achieved energy density e(t) decreases with the evolution time t as e(t) - e(infinity) = h(log(10)t)(-z) with a small prefactor h and a scaling coefficient z > 1, indicating an energy landscape with deep and rugged funnel-shape regions. For the +/- J Viana-Bray spin glass model, however, the greedy single-spin dynamics quickly gets trapped to a local minimal region of the energy landscape.
学科主题	Physics
收录类别	SCI
资助信息	NSFC [10774150, 10834014]; 973-Program [2007CB935903]
原文出处	http://dx.doi.org/10.1103/PhysRevE.83.052101
语种	英语
WOS记录号	WOS:000290156000006
公开日期	2013-05-17
内容类型	期刊论文
源URL	[http://ir.itp.ac.cn/handle/311006/14357]
专题	理论物理研究所_理论物理所1978-2010年知识产出
推荐引用方式 GB/T 7714	Zhou, HJ. Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process[J]. PHYSICAL REVIEW E,2011,83(5):52101.
APA	Zhou, HJ.(2011).Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process.PHYSICAL REVIEW E,83(5),52101.
MLA	Zhou, HJ."Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process".PHYSICAL REVIEW E 83.5(2011):52101.