Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
From MaRDI portal
Publication:328683
DOI10.1007/s10878-015-9891-9zbMath1354.90120OpenAlexW562761389MaRDI QIDQ328683
Publication date: 20 October 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-015-9891-9
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- An upper (lower) bound for Max (Min) CSP
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- 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
- Analyzing Walksat on Random Formulas
- Two Hardness Results on Feedback Vertex Sets
- A Model to Study Phase Transition and Plateaus in Relational Learning
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Tail bounds for occupancy and the satisfiability threshold conjecture
- A Note on Treewidth in Random Graphs
- Theory and Applications of Satisfiability Testing
- Large Hypertree Width for Sparse Random Hypergraphs
- Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
- Random constraint satisfaction: A more accurate picture
- Random constraint satisfaction: Flaws and structure
- Constructing an asymptotic phase transition in random binary constraint satisfaction problems
- Bounding the scaling window of random constraint satisfaction problems
This page was built for publication: Performances of pure random walk algorithms on constraint satisfaction problems with growing domains