Bounding the scaling window of random constraint satisfaction problems

DOI10.1007/s10878-014-9789-yzbMath1360.90174OpenAlexW1966203790MaRDI QIDQ5963651

Jing Shen, Yao-Feng Ren

Publication date: 23 February 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-014-9789-y

zbMATH Keywords

phase transitionconstraint satisfaction problemfinite-size scaling analysis

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items

Performances of pure random walk algorithms on constraint satisfaction problems with growing domains, Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A general model and thresholds for random constraint satisfaction problems
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• On the constraint length of random \(k\)-CSP
• Many hard examples in exact phase transitions
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Locating the phase transition in binary constraint satisfaction problems
• The scaling window of the 2-SAT transition
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Models and thresholds for random constraint satisfaction problems
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Large Hypertree Width for Sparse Random Hypergraphs
• Probability and Computing
• Random constraint satisfaction: A more accurate picture