The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT

DOI10.1016/j.disopt.2010.07.003zbMath1248.90067OpenAlexW2017619848MaRDI QIDQ456705

Stefan Szeider

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.07.003

zbMATH Keywords

local searchmaximum satisfiabilityparameterized complexity

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (11)

Complexity and approximability of parameterized MAX-CSPs ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints ⋮ Fast local search methods for solving limited memory influence diagrams ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ On the complexity of restoring corrupted colorings ⋮ Local search: is brute-force avoidable? ⋮ Local search for string problems: brute-force is essentially optimal ⋮ Searching for better fill-in ⋮ Minimizing Rosenthal potential in multicast games

Cites Work

• Unnamed Item
• Unnamed Item
• A simplified NP-complete MAXSAT problem
• Local search: is brute-force avoidable?
• A simplified NP-complete satisfiability problem
• On miniaturized problems in parameterized complexity theory
• Searching the \(k\)-change neighborhood for TSP is W[1-hard]
• On problems without polynomial kernels
• 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
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Deciding first-order properties of locally tree-decomposable structures
• On the Hardness of Losing Weight
• The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
• Stable Assignment with Couples: Parameterized Complexity and Local Search
• 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