A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
type: Item
instance of: scholarly article
title: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
zbMATH Open document ID: 1061.68071
DOI: 10.1016/S0304-3975(01)00174-8
author: E. Ya. Dantsin
author: Andreas Goerdt
author: Edward A. Hirsch
author: Christos Papadimitriou
author: Prabhakar Raghavan
author: R. Kannan
author: Jon M. Kleinberg
author: Uwe Schöning
published in: Theoretical Computer Science
publication date: 2003-01-21T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1857084
MaRDI profile type: Publication
Wikidata QID: Q57904544
cites work: Q5516510
cites work: Q4004338
cites work: Q4342497
cites work: Q4525695
cites work: New worst-case upper bounds for SAT
cites work: SAT local search algorithms: Worst-case study
cites work: On the greedy algorithm for satisfiability
cites work: Q4375761
cites work: New methods for 3-SAT decision and worst-case analysis
cites work: Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
cites work: Solving satisfiability in less than \(2^ n\) steps
cites work: An improved exponential-time algorithm for k -SAT
cites work: Q4484662
cites work: Number of models and satisfiability of sets of clauses
full work available at URL: s0304-3975(01)00174-8
OpenAlex ID: W2171680292
Recommended article: Q4779137
Recommended article: Q2754147
Recommended article: A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
Recommended article: Q4224926
Recommended article: An improved deterministic local search algorithm for 3-SAT
Recommended article: Local search algorithms for SAT: an empirical evaluation
Recommended article: Q4578331
Recommended article: An approximation algorithm for \(\#k\)-SAT
description: scientific article; zbMATH DE number 1857084