Analysis of local search landscapes for \(k\)-SAT instances

DOI10.1007/s11786-010-0040-7zbMath1205.90237OpenAlexW2168379232MaRDI QIDQ626907

K. Steinhöfel, Andreas A. Albrecht, Peter C. R. Lane

Publication date: 19 February 2011

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11786-010-0040-7

zbMATH Keywords

phase transitionlocal searchgamma distributionSAT problemcombinatorial landscapes

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete mathematics in relation to computer science (68R99)

Uses Software

• BG-WalkSAT
• ChainSAT

Cites Work

• An improved deterministic local search algorithm for 3-SAT
• Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability
• A guided tour of Chernoff bounds
• On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries
• Stochastic protein folding simulation in the three-dimensional HP-model
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• Towards a characterisation of the behaviour of stochastic local search algorithms for SAT
• Planning as propositional CSP: From Walksat to local search techniques for action graphs
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• A stopping criterion for logarithmic simulated annealing
• Combinatorial Landscapes
• Efficiency of Local Search with Multiple Local Optima
• Opportunities for Combinatorial Optimization in Computational Biology
• A Remark on Stirling's Formula
• An efficient local search method for random 3-satisfiability
• An improved exponential-time algorithm for k -SAT
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Statistical analysis of local search landscapes
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Local search characteristics of incomplete SAT procedures
• Statistical mechanics methods and phase transitions in optimization problems

This page was built for publication: Analysis of local search landscapes for \(k\)-SAT instances