Name
Abstract | ||
|---|---|---|
This paper analyzes the scaling window of a random CSP model (i.e. model RB) for which we can identify the threshold points exactly, denoted by rcr or pcr. For this model, we establish the scaling window W(n,�) = (r (n,�), r+(n,�)) such that the probability of a random instance being satisfiable is greater than 1 � for r < r (n,�) and is less thanfor r > r+(n,�). Specifically, we obtain the following result W(n,�) = (rcr �( 1 n1 " lnn ), r cr + �( 1 nlnn )), where 0 � " < 1 is a constant. A similar result with respect to the other parameter p is also obtained. Since the instances generated by model RB have been shown to be hard at the threshold, this is the first attempt, as far as we know, to analyze the scaling window of such a model with hard instances. |
Year | Venue | Keywords |
|---|---|---|
2008 | Clinical Orthopaedics and Related Research | satisfiability,scaling window.,. constraint satisfaction problem,phase transition,model rb,constraint satisfaction problem |
DocType | Volume | Citations |
Journal | abs/0801.3 | 0 |
PageRank | References | Authors |
0.34 | 11 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chunyan Zhao | 1 | 3 | 1.06 |
| Ke Xu | 2 | 1433 | 99.79 |
| Zhiming Zheng | 3 | 128 | 16.80 |