Performances of pure random walk algorithms on constraint satisfaction problems with growing domains

DOI10.1007/s10878-015-9891-9zbMath1354.90120OpenAlexW562761389MaRDI QIDQ328683

Wei Xu, Fu-Zhou Gong

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

zbMATH Keywords

random walkconstraint satisfaction problemslocal search algorithmsmodel RB

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Randomized algorithms (68W20)

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