A deterministic (2-2/(k+1))^n algorithm for k-SAT based on local search.
From MaRDI portal
Publication:1853552
DOI10.1016/S0304-3975(01)00174-8zbMATH Open1061.68071OpenAlexW2171680292WikidataQ57904544 ScholiaQ57904544MaRDI QIDQ1853552FDOQ1853552
Authors: E. Ya. Dantsin, Andreas Goerdt, Edward A. Hirsch, Christos Papadimitriou, Prabhakar Raghavan, R. Kannan, Jon M. Kleinberg, Uwe Schöning 
Publication date: 21 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00174-8
Recommendations
- scientific article; zbMATH DE number 1834642
- scientific article; zbMATH DE number 1670827
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- scientific article; zbMATH DE number 1241386
- An improved deterministic local search algorithm for 3-SAT
- Local search algorithms for SAT: an empirical evaluation
- Local search algorithms for SAT: an empirical evaluation
- Local maxima and improved exact algorithm for MAX-2-SAT
- An approximation algorithm for \(\#k\)-SAT
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Solving satisfiability in less than \(2^ n\) steps
- Title not available (Why is that?)
- Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
- New methods for 3-SAT decision and worst-case analysis
- An improved exponential-time algorithm for k -SAT
- Title not available (Why is that?)
- New worst-case upper bounds for SAT
- Number of models and satisfiability of sets of clauses
- On the greedy algorithm for satisfiability
- SAT local search algorithms: Worst-case study
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (53)
- An improved local search algorithm for 3-SAT
- Exact Algorithms for MAX-SAT
- An efficient fixed-parameter algorithm for 3-hitting set
- Solving SAT for CNF Formulas with a One-Sided Restriction on Variable Occurrences
- The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
- Title not available (Why is that?)
- An efficient local search method for random 3-satisfiability
- Worst-case study of local search for MAX-\(k\)-SAT.
- Strong ETH and resolution via games and the multiplicity of strategies
- Title not available (Why is that?)
- Improving exact algorithms for MAX-2-SAT
- A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
- Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
- Local Reductions
- Density condensation of Boolean formulas
- Theory and Applications of Satisfiability Testing
- Computing branchwidth via efficient triangulations and blocks
- An improved exponential-time algorithm for k -SAT
- Local reduction
- Algorithms for four variants of the exact satisfiability problem
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- Exploiting partial knowledge of satisfying assignments
- Unrestricted vs restricted cut in a tableau method for Boolean circuits
- The complexity of Boolean constraint satisfaction local search problems
- SAT local search algorithms: Worst-case study
- Sequential vector packing
- A note on the complexity of minimum dominating set
- On converting CNF to DNF
- Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems
- Comparing the succinctness of monadic query languages over finite trees
- Solving NP-Complete Problems with Quantum Search
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- Improved agreeing-gluing algorithm
- The resolution complexity of random graph \(k\)-colorability
- An Empirical Study of MAX-2-SAT Phase Transitions
- Derandomizing the HSSW algorithm for 3-SAT
- Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
- Solving connected dominating set faster than \(2^n\)
- A new upper bound for \(( n , 3)\)-MAX-SAT
- A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
- Modelling the dynamics of stochastic local search on \(k\)-SAT
- Using small-scale quantum devices to solve algebraic equations
- Local search algorithms for SAT: Worst-case analysis
- UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
- Title not available (Why is that?)
- Satisfiability certificates verifiable in subexponential time
- Guided Search and a Faster Deterministic Algorithm for 3-SAT
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Improved exact algorithms for MAX-SAT
- An initial study of time complexity in infinite-domain constraint satisfaction
- An improved upper bound for SAT
- A randomized algorithm for 3-SAT
- An improved deterministic local search algorithm for 3-SAT
This page was built for publication: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853552)
