Bounding the scaling window of random constraint satisfaction problems

DOI10.1007/S10878-014-9789-YMaRDI QIDQ5963651zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

phase transitionconstraint satisfaction problemfinite-size scaling analysis

Mathematics Subject Classification ID

Integer programming (90C10)

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

Cites work

• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• A general model and thresholds for random constraint satisfaction problems
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Large hypertree width for sparse random hypergraphs
• Locating the phase transition in binary constraint satisfaction problems
• Many hard examples in exact phase transitions
• Models and thresholds for random constraint satisfaction problems
• On the constraint length of random \(k\)-CSP
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Probability and Computing
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• The scaling window of the 2-SAT transition
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions

Cited in

(5)

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

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)