Analyzing Walksat on Random Formulas

Analyzing Walksat on Random Formulas
复制标题

DOI：
10.1137/12090191x
复制
发表时间：
2011-06
期刊：
--
影响因子：
--
通讯作者：
A. Coja-Oghlan;A. Frieze
A. Coja-Oghlan;A. Frieze
中科院分区：
其他
文献类型：
--
作者：
A. Coja-Oghlan;A. Frieze

文献摘要

被引文献

相似文献

设Φ是n个变量m个子句的均匀分布随机k-SAT公式。我们证明了Papadimitriou（FOCS 1991）/Schoning（FOCS 1999）的Walksat算法在多项式时间w. h. p.内找到一个令人满意的Φ的分配，如果m/n ≤ ρ · 2k/k，对于某个常数ρ > 0.这比Coja-Oghlan、Feige、Frieze、Krivelevich、Vilenchik之前对Walksat的最佳分析（SODA 2009）提高了一个因子θ（k）。
Let Φ be a uniformly distributed random k-SAT formula with n variables and m clauses. We prove that the Walksat algorithm from Papadimitriou (FOCS 1991)/Schoning (FOCS 1999) finds a satisfying assignment of Φ in polynomial time w.h.p. if m/n ≤ ρ · 2k/k for a certain constant ρ > 0. This is an improvement by a factor of Θ(k) over the best previous analysis of Walksat from Coja-Oghlan, Feige, Frieze, Krivelevich, Vilenchik (SODA 2009).