The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
From MaRDI portal
Publication:3637173
DOI10.1007/978-3-642-02777-2_27zbMath1247.68262MaRDI QIDQ3637173
Publication date: 7 July 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02777-2_27
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Constraint Satisfaction Parameterized by Solution Size
Cites Work
- Searching the \(k\)-change neighborhood for TSP is W[1-hard]
- How easy is local search?
- Analyses on the 2 and 3-flip neighborhoods for the MAX SAT
- Which problems have strongly exponential complexity?
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Parametrized complexity theory.
- Deciding first-order properties of locally tree-decomposable structures
- On the Hardness of Losing Weight
- On Local Search and Placement of Meters in Networks
- Graph-Theoretic Concepts in Computer Science
- Unnamed Item