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

doi:10.1016/j.physa.2019.122708

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	Clustering phase of a general constraint satisfaction problem model d-k-CSP
	Xu, Wei 1; Gong, Fuzhou 3; Zhou, Guangyan 2
刊名	PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS
	2020
卷号	537 页码:15
关键词	Constraint satisfaction problem Solution space structure Clustering phase transition Problem hardness Belief propagation
ISSN号	0378-4371
DOI	10.1016/j.physa.2019.122708
英文摘要	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.
资助项目	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
语种	英语
出版者	ELSEVIER
WOS记录号	WOS:000501641200067
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/50421]
专题	应用数学研究所
通讯作者	Zhou, Guangyan
作者单位	1.Univ Sci & Technol Beijing, Sch Math & Phys, Beijing 100083, Peoples R China 2.Beijing Technol & Business Univ, Dept Math, Beijing 100048, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing 100190, 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.