Bounding the scaling window of random constraint satisfaction problems

DOI10.1007/S10878-014-9789-YzbMATH Open1360.90174OpenAlexW1966203790MaRDI QIDQ5963651FDOQ5963651

Authors: Jing Shen, Yaofeng 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

Recommendations

• The scaling window of the model \(d\)-\(k\)-CSP
• Models for Random Constraint Satisfaction Problems
• On the phase transitions of random \(k\)-constraint satisfaction problems
• A general model and thresholds for random constraint satisfaction problems
• On the constraint length of random \(k\)-CSP

zbMATH Keywords

phase transitionconstraint satisfaction problemfinite-size scaling analysis

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

• Probability and Computing
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• 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
• Locating the phase transition in binary constraint satisfaction problems
• A general model and thresholds for random constraint satisfaction problems
• Title not available (Why is that?)
• Large hypertree width for sparse random hypergraphs
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Random constraint satisfaction: A more accurate picture
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Models and thresholds for random constraint satisfaction problems
• Title not available (Why is that?)
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• The scaling window of the 2-SAT transition
• Title not available (Why is that?)

Cited In (5)

• Critical window of the symmetric perceptron
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• The scaling window of the model \(d\)-\(k\)-CSP
• Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
• Singletons for simpletons revisiting windowed backoff with Chernoff bounds

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963651)