| An upper （lower） bound for Max （Min） CSP |
| |
| 作者姓名： | HUANG Ping ;YIN MingHao |
| |
| 作者单位： | [1]School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China; [2]School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China |
| |
| 基金项目： | Acknowledgements This research was supported by Program for New Century Excellent Talents in University （Grant No. NCET-13- 0724）, Natural Science Foundation of Jilin Province （Grant No. 201215006）, and Natural Science Foundation of China （Grant Nos. 61370156, 61370052）. |
| |
| 摘 要： | The random constraint satisfaction problem(CSP)instances generated by Model RB have been widely used in the field of CSP and have some nice features.In this paper,we consider two optimization versions of CSP,i.e.,the maximum constraint satisfaction problem(Max-CSP)and the minimum satisfaction problem(Min-CSP)of Model RB.The problem of the Max-CSP is how to find an assignment to all the variables such that the maximum number of constraints are satisfied and the problem of Min-CSP is how to find an assignment to all the variables such that the minimum number of constraints are satisfied.We use the first moment method to prove that when r2α(1/p-1)(or p2α/(2α+r)),an upper bound of Max-CSP can be derived.Similarly,we can prove that when r2α(1/p-1)(or p2α/(2α+r)),a lower bound of Min-CSP can be derived.
|
| 关 键 词： | Max CSP Min CSP RB model upper bound lower bound |
An upper (lower) bound for Max (Min) CSP |
| |
| HUANG Ping,;YIN MingHao.An upper (lower) bound for Max (Min) CSP[J].SCIENCE CHINA Information Sciences,2014,57(7):1-9. |
| |
| Authors: | Ping Huang MingHao Yin |
| |
| Affiliation: | 1. School of Electronics Engineering and Computer Science, Peking University, Beijing, 100871, China
2. School of Computer Science and Information Technology, Northeast Normal University, Changchun, 130117, China
|
| |
| Abstract: | Max CSP, Min CSP, RB model, upper bound, lower bound |
| |
| Keywords: | Max CSP Min CSP RB model upper bound lower bound |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
|
