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, 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
