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 (2)

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

This page was built for publication: Bounding the scaling window of random constraint satisfaction problems