Bounding the scaling window of random constraint satisfaction problems

被引:0
作者
Jing Shen
Yaofeng Ren
机构
[1] Naval University of Engineering,College of Science
来源
Journal of Combinatorial Optimization | 2016年 / 31卷
关键词
Constraint satisfaction problem; Phase transition; Finite-size scaling analysis;
D O I
暂无
中图分类号
学科分类号
摘要
The model k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-CSP is a random CSP model with moderately growing arity k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document} of constraints. By incorporating certain linear structure, k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-CSP is revised to a random linear CSP, named k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-hyper-F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb F}$$\end{document}-linear CSP. It had been shown theoretically that the two models exhibit exact satisfiability phase transitions when the constraint density r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r$$\end{document} is varied accordingly. In this paper, we use finite-size scaling analysis to characterize the threshold behaviors of the two models with finite problem size n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document}. A series of experimental studies are carried out to illustrate the scaling window of the model k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-CSP.
引用
收藏
页码:786 / 801
页数:15
相关论文
共 27 条
  • [1] Achlioptas D(2005)-matrices and the magic square. Rigorous location of phase transitions in hard optimization problems Nature 435 759-764
  • [2] Naor A(2001)The scaling window of the 2-sat transition Random Struct Algorithms 18 201-256
  • [3] Peres Y(2011)On the phase transitions of random k-constraint satisfaction problems Artif Intell 175 914-927
  • [4] Bollobás B(2012)A general model and thresholds for random constraint satisfaction problems Artif Intell 193 1-17
  • [5] Borgs C(1996)Analysis of two simple heuristics on a random instance of k-sat J Algorithms 20 312-355
  • [6] Chayes JT(1994)Critical behavior in the satisfiability of random boolean formulae Science 264 1297-1301
  • [7] Kim JH(1996)Locating the phase transition in binary constraint satisfaction problems Artif Intell 81 155-181
  • [8] Wilson DB(2007)Random constraint satisfaction: easy generation of hard (satisfiable) instances Artif Intell 171 514-534
  • [9] Fan Y(2000)Exact phase transitions in random constraint satisfaction problems J Artif Intell Res 12 93-103
  • [10] Shen J(2006)Many hard examples in exact phase transitions Theor Comput Sci 355 291-302