A BETTER ALGORITHM FOR RANDOM k-SAT

被引：40

作者：

Coja-Oghlan, Amin ^{[1
,2
]}

机构：

[1] Univ Warwick, Inst Math, Coventry CV4 7AL, W Midlands, England

[2] Univ Warwick, Dept Comp Sci, Coventry CV4 7AL, W Midlands, England

来源：

SIAM JOURNAL ON COMPUTING | 2010年 / 39卷 / 07期

基金：

英国工程与自然科学研究理事会;

关键词：

random structures; efficient algorithms; phase transitions; k-SAT; PROBABILISTIC ANALYSIS; SURVEY PROPAGATION; HEURISTICS;

D O I：

10.1137/09076516X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let Phi be a uniformly distributed random k-SAT formula with n variables and m clauses. We present a polynomial time algorithm that finds a satisfying assignment of Phi with high probability for constraint densities m/n < (1 - epsilon(k))2(k) ln(k)/k, where epsilon(k) -> 0. Previously no efficient algorithm was known to find satisfying assignments with a nonvanishing probability beyond m/n = 1.817 . 2(k)/k [A. Frieze and S. Suen, J. Algorithms, 20 (1996), pp. 312-355].

引用

页码：2823 / 2864

页数：42

共 50 条

[1] A Better Algorithm for Random k-SAT
Coja-Oghlan, Amin
AUTOMATA, LANGUAGES AND PROGRAMMING, PT I, 2009, 5555 : 292 - 303
[2] Polarised random k-SAT
Danielsson, Joel Larsson
Markstrom, Klas
COMBINATORICS PROBABILITY AND COMPUTING, 2023, 32 (06) : 885 - 899
[3] Biased random k-SAT
Larsson, Joel
Markstrom, Klas
RANDOM STRUCTURES & ALGORITHMS, 2021, 59 (02) : 238 - 266
[4] An Approximation Algorithm for #k-SAT
Thurley, Marc
29TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, (STACS 2012), 2012, 14 : 78 - 87
[5] On an online random k-SAT model
Kravitz, David
RANDOM STRUCTURES & ALGORITHMS, 2008, 32 (01) : 115 - 124
[6] On the behaviour of random K-SAT on trees
Krishnamurthy, Supriya
Sumedha
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2012,
[7] The Decimation Process in Random k-SAT
Coja-Oghlan, Amin
Pachon-Pinzon, Angelica Y.
Automata, Languages and Programming, ICALP, Pt I, 2011, 6755 : 305 - 316
[8] THE DECIMATION PROCESS IN RANDOM k-SAT
Coja-Oghlan, Amin
Pachon-Pinzon, Angelica Y.
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (04) : 1471 - 1509
[9] Analysis of backtracking of random k-SAT
Xu, Ke
Li, Wei
Jisuanji Xuebao/Chinese Journal of Computers, 2000, 23 (05): : 454 - 458
[10] On the critical exponents of random k-SAT
Wilson, DB
RANDOM STRUCTURES & ALGORITHMS, 2002, 21 (02) : 182 - 195

← 1 2 3 4 5 →