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

DOI10.1007/S10878-015-9891-9zbMATH Open1354.90120OpenAlexW562761389MaRDI QIDQ328683FDOQ328683

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

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

zbMATH Keywords

random walkconstraint satisfaction problemslocal search algorithmsmodel RB

Mathematics Subject Classification ID

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

Cites Work

• Handbook of constraint programming.
• Two Hardness Results on Feedback Vertex Sets
• 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
• Title not available (Why is that?)
• A Model to Study Phase Transition and Plateaus in Relational Learning
• A general model and thresholds for random constraint satisfaction problems
• Title not available (Why is that?)
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Title not available (Why is that?)
• Tail bounds for occupancy and the satisfiability threshold conjecture
• Title not available (Why is that?)
• 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
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Title not available (Why is that?)
• 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
• An upper (lower) bound for Max (Min) CSP

Cited In (2)

• Theory and Applications of Satisfiability Testing
• Gap Amplification in PCPs Using Lazy Random Walks

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)