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

DOI10.1007/S10878-015-9891-9MaRDI QIDQ328683zbMATH OpenOpenAlexFDO

Authors Fuzhou Gong, Wei Xu

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

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

Recommendations

• A study of pure random walk algorithms on constraint satisfaction problems with growing domains
• scientific article; zbMATH DE number 1002207
• Randomized approximation of the constraint satisfaction problem
• An analysis of backtrack-free algorithms on a constraint satisfaction problem with growing domains
• Theory and Applications of Satisfiability Testing
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Bounding the scaling window of random constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• scientific article; zbMATH DE number 5547880 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• A Model to Study Phase Transition and Plateaus in Relational Learning
• A general model and thresholds for random constraint satisfaction problems
• A note on treewidth in random graphs
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• An analysis of backtrack-free algorithms on a constraint satisfaction problem with growing domains
• An upper (lower) bound for Max (Min) CSP
• Analyzing Walksat on random formulas
• Bounding the scaling window of random constraint satisfaction problems
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems
• Handbook of constraint programming.
• Large hypertree width for sparse random hypergraphs
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• Locating the phase transition in binary constraint satisfaction problems
• Many hard examples in exact phase transitions
• On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
• On the constraint length of random \(k\)-CSP
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: Flaws and structure
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Tail bounds for occupancy and the satisfiability threshold conjecture
• Theory and Applications of Satisfiability Testing
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• Two Hardness Results on Feedback Vertex Sets

Cited in

(3)

• Theory and Applications of Satisfiability Testing
• Gap Amplification in PCPs Using Lazy Random Walks
• A study of pure random walk algorithms on constraint satisfaction problems with growing domains

This page was built for publication: Performances of pure random walk algorithms on constraint satisfaction problems with growing domains

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