WALKSAT IS LINEAR ON RANDOM 2-SAT

作     者：Berenbrink, Petra Coja-Oghlan, Amin Cooper, Colin Götte, Thorsten Hintze, Lukas Zakharov, Pavel 

作者机构：UNIVERSITY OF HAMBURG FACULTY OF MATHEMATICS INFORMATICS AND NATURAL SCIENCES DEPARTMENT OF INFORMATICS VOGT-KÖLLN-STR. 30 Hamburg22527 Germany TU DORTMUND FACULTY OF COMPUTER SCIENCE AND FACULTY OF MATHEMATICS 12 OTTO-HAHN-ST Dortmund44227 Germany DEPARTMENT OF INFORMATICS KING’S COLLEGE UNIVERSITY OF LONDON LondonWC2B 4BG United Kingdom 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Local search (optimization) 

摘      要：MSC Codes 68Q87, 60C05In an influential article Papadimitriou [FOCS 1991] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with n variables in O(n2) expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (e.g., [Hoos and Stützle 2000]). In the present article we analyse the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [SICOMP 2007], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold. Copyright © 2024, The Authors. All rights reserved.