Worst-case study of local search for MAX-\(k\)-SAT.
From MaRDI portal
Publication:1408379
DOI10.1016/S0166-218X(02)00404-3zbMath1051.68079MaRDI QIDQ1408379
Publication date: 15 September 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
Related Items
An exponential time 2-approximation algorithm for bandwidth, Approximating MAX SAT by moderately exponential and parameterized algorithms, Solving sparse instances of Max SAT via width reduction and greedy restriction, Improved exact algorithms for mildly sparse instances of MAX SAT, A new algorithm for optimal 2-constraint satisfaction and its implications, Moderately exponential time and fixed parameter approximation algorithms
Uses Software
Cites Work
- Algorithms for the maximum satisfiability problem
- Solving satisfiability in less than \(2^ n\) steps
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- New worst-case upper bounds for SAT
- Local search algorithms for SAT: an empirical evaluation
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- SAT local search algorithms: Worst-case study
- An improved exponential-time algorithm for k -SAT
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- On the Approximation of Maximum Satisfiability
- New Upper Bounds for Maximum Satisfiability
- Algorithmic aspects in speech recognition
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item