Worst-case study of local search for MAX-\(k\)-SAT.

DOI10.1016/S0166-218X(02)00404-3zbMath1051.68079MaRDI QIDQ1408379

Edward A. Hirsch

Publication date: 15 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

MAX-SATPapadimitriou algorithmSchöning algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (6)

Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Moderately exponential time and fixed parameter approximation algorithms

Uses Software

• MAX-2-SAT
• Walksat
• zChaff
• Chaff

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

This page was built for publication: Worst-case study of local search for MAX-\(k\)-SAT.