Clustering phase of a general constraint satisfaction problem model d-k-CSP

doi:10.1016/j.physa.2019.122708

CSpace > 应用数学研究所

	Clustering phase of a general constraint satisfaction problem model d-k-CSP
	Xu, Wei 1; Gong, Fuzhou2 ; Zhou, Guangyan 3
	2020
发表期刊	PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS
ISSN	0378-4371
卷号	537 页码:15
摘要	Relation between problem hardness and solution space structure is an important research aspect. Model d-k-CSP is a random model of constraint satisfaction problem, which generates very hard instances when r = 1 or r is near 1, where r represents normalized constraint density. We study the clustering phase of the model, and find that if r is below and close to 1, the solution space contains many widely distributed and well-separated small frozen clusters, which should be the reason why the generated instances are hard to solve. (C) 2019 Elsevier B.V. All rights reserved.
关键词	Constraint satisfaction problem Solution space structure Clustering phase transition Problem hardness Belief propagation
DOI	10.1016/j.physa.2019.122708
收录类别	SCI
语种	英语
资助项目	Fundamental Research Funds for the Central Universities[FRF-TP-16-065A1] ; National Natural Science Foundation of China[11801028] ; National Natural Science Foundation of China[61702019]
WOS研究方向	Physics
WOS类目	Physics, Multidisciplinary
WOS记录号	WOS:000501641200067
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/50422
专题	应用数学研究所
通讯作者	Zhou, Guangyan
作者单位	1.Univ Sci & Technol Beijing, Sch Math & Phys, Beijing 100083, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100190, Peoples R China 3.Beijing Technol & Business Univ, Dept Math, Beijing 100048, Peoples R China
推荐引用方式 GB/T 7714	Xu, Wei,Gong, Fuzhou,Zhou, Guangyan. Clustering phase of a general constraint satisfaction problem model d-k-CSP[J]. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS,2020,537:15.
APA	Xu, Wei,Gong, Fuzhou,&Zhou, Guangyan.(2020).Clustering phase of a general constraint satisfaction problem model d-k-CSP.PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS,537,15.
MLA	Xu, Wei,et al."Clustering phase of a general constraint satisfaction problem model d-k-CSP".PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 537(2020):15.