ITP OpenIR  > 理论物理所科研产出  > SCI论文
Zhao, CY; Zhou, HJ; Zheng, ZM; Xu, K; Xu, K (reprint author), Beihang Univ, State Key Lab Software Dev Environm, Beijing 100191, Peoples R China.
A message-passing approach to random constraint satisfaction problems with growing domains
Source PublicationJOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Language英语
KeywordExact Phase-transitions Random K-sat Satisfiability Threshold Algorithm
AbstractMessage-passing algorithms based on belief propagation (BP) are implemented on a random constraint satisfaction problem (CSP) referred to as model RB, which is a prototype of hard random CSPs with growing domain size. In model RB, the number of candidate discrete values (the domain size) of each variable increases polynomially with the variable number N of the problem formula. Although the satisfiability threshold of model RB is exactly known, finding solutions for a single problem formula is quite challenging and attempts have been limited to cases of N similar to 10(2). In this paper, we propose two different kinds of message-passing algorithms guided by BP for this problem. Numerical simulations demonstrate that these algorithms allow us to find a solution for random formulas of model RB with constraint tightness slightly less than p(cr), the threshold value for the satisfiability phase transition. To evaluate the performance of these algorithms, we also provide a local search algorithm (random walk) as a comparison. Besides this, the simulated time dependence of the problem size N and the entropy of the variables for growing domain size are discussed.
2011
ISSN1742-5468
Issue*Pages:P02019
Subject AreaPhysics
Indexed BySCI
Funding OrganizationNational Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033] ; National Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033] ; National Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033] ; National Key Basic Research Project of China [200532CB1092]; NSFC [60473109, 60973033]
Citation statistics
Cited Times:3[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/14422
Collection理论物理所科研产出_SCI论文
Corresponding AuthorXu, K (reprint author), Beihang Univ, State Key Lab Software Dev Environm, Beijing 100191, Peoples R China.
Recommended Citation
GB/T 7714
Zhao, CY,Zhou, HJ,Zheng, ZM,et al. A message-passing approach to random constraint satisfaction problems with growing domains[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,2011(*):P02019.
APA Zhao, CY,Zhou, HJ,Zheng, ZM,Xu, K,&Xu, K .(2011).A message-passing approach to random constraint satisfaction problems with growing domains.JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT(*),P02019.
MLA Zhao, CY,et al."A message-passing approach to random constraint satisfaction problems with growing domains".JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT .*(2011):P02019.
Files in This Item:
File Name/Size DocType Version Access License
A message-passing ap(810KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhao, CY]'s Articles
[Zhou, HJ]'s Articles
[Zheng, ZM]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhao, CY]'s Articles
[Zhou, HJ]'s Articles
[Zheng, ZM]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhao, CY]'s Articles
[Zhou, HJ]'s Articles
[Zheng, ZM]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.