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.68262OpenAlexW184791457MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (2)
The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Constraint Satisfaction Parameterized by Solution Size
Cites Work
- Unnamed Item
- 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
This page was built for publication: The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
