A novel local search based on variable-focusing for random K-SAT

2013/10/09 by Rémi Lemoy, Lemoy, Rémi, Mikko Alava +3
Computer Science · Physics and Astronomy · #Artificial Intelligence (cs.AI) #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #cond-mat.dis-nn #cs.AI

paper · pdf · doi:10.48550/arxiv.1311.2914

7 pages, 3 figures

arxiv created 2013/12/12 · arxiv updated 2013/12/13

Abstract

We introduce a new local search algorithm for satisfiability problems. Usual approaches focus uniformly on unsatisfied clauses. The new method works by picking uniformly random variables in unsatisfied clauses. A Variable-based Focused Metropolis Search (V-FMS) is then applied to random 3-SAT. We show that it is quite comparable in performance to the clause-based FMS. Consequences for algorithmic design are discussed.

Related

• Evolving difficult SAT instances thanks to local search
• Phase transition for Local Search on planted SAT
• Local equations describe unreasonably efficient stochastic algorithms in random K-SAT
• Improving probability selecting based weights for Satisfiability Problem
• Single-solution Random 3-SAT Instances