Standard

A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search. / Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe.

In: Theoretical Computer Science, Vol. 289, No. 1, 23.10.2002, p. 69-83.

Research output: Contribution to journal › Article › peer-review

Harvard

Dantsin, E, Goerdt, A, Hirsch, EA, Kannan, R, Kleinberg, J, Papadimitriou, C, Raghavan, P & Schöning, U 2002, 'A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search', Theoretical Computer Science, vol. 289, no. 1, pp. 69-83. https://doi.org/10.1016/S0304-3975(01)00174-8

APA

Dantsin, E., Goerdt, A., Hirsch, E. A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., & Schöning, U. (2002). A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search. Theoretical Computer Science, 289(1), 69-83. https://doi.org/10.1016/S0304-3975(01)00174-8

Vancouver

Dantsin E, Goerdt A, Hirsch EA, Kannan R, Kleinberg J, Papadimitriou C et al. A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search. Theoretical Computer Science. 2002 Oct 23;289(1):69-83. https://doi.org/10.1016/S0304-3975(01)00174-8

Author

Dantsin, Evgeny ; Goerdt, Andreas ; Hirsch, Edward A. ; Kannan, Ravi ; Kleinberg, Jon ; Papadimitriou, Christos ; Raghavan, Prabhakar ; Schöning, Uwe. / A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search. In: Theoretical Computer Science. 2002 ; Vol. 289, No. 1. pp. 69-83.

BibTeX

@article{e89a5889b687438485f5f7d950ed6d28,
title = "A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search",
abstract = "Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Sch{\"o}ning (1999) proved that a close algorithm for k-SAT takes time (2 - 2/k)n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.). We describe a deterministic local search algorithm for k-SAT running in time (2 - 2/(k + 1))n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other {"}weakly exponential{"} algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.",
author = "Evgeny Dantsin and Andreas Goerdt and Hirsch, {Edward A.} and Ravi Kannan and Jon Kleinberg and Christos Papadimitriou and Prabhakar Raghavan and Uwe Sch{\"o}ning",
year = "2002",
month = oct,
day = "23",
doi = "10.1016/S0304-3975(01)00174-8",
language = "English",
volume = "289",
pages = "69--83",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1",

}

RIS

TY - JOUR

T1 - A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search

AU - Dantsin, Evgeny

AU - Goerdt, Andreas

AU - Hirsch, Edward A.

AU - Kannan, Ravi

AU - Kleinberg, Jon

AU - Papadimitriou, Christos

AU - Raghavan, Prabhakar

AU - Schöning, Uwe

PY - 2002/10/23

Y1 - 2002/10/23

N2 - Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schöning (1999) proved that a close algorithm for k-SAT takes time (2 - 2/k)n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.). We describe a deterministic local search algorithm for k-SAT running in time (2 - 2/(k + 1))n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.

AB - Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schöning (1999) proved that a close algorithm for k-SAT takes time (2 - 2/k)n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.). We describe a deterministic local search algorithm for k-SAT running in time (2 - 2/(k + 1))n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.

UR - http://www.scopus.com/inward/record.url?scp=0037163951&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(01)00174-8

DO - 10.1016/S0304-3975(01)00174-8

M3 - Article

AN - SCOPUS:0037163951

VL - 289

SP - 69

EP - 83

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1

ER -

ID: 49829226