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

DOI10.1016/J.DISOPT.2010.07.003MaRDI QIDQ456705zbMATH OpenOpenAlexFDO

Authors 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 searchparameterized complexitymaximum satisfiability

Mathematics Subject Classification ID

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

Recommendations

• The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
• Analyses on the 2 and 3-flip neighborhoods for the MAX SAT
• scientific article; zbMATH DE number 1222824
• Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental Evaluation
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A simplified NP-complete MAXSAT problem
• A simplified NP-complete satisfiability problem
• Analyses on the 2 and 3-flip neighborhoods for the MAX SAT
• Deciding first-order properties of locally tree-decomposable structures
• Graph-Theoretic Concepts in Computer Science
• Local search: is brute-force avoidable?
• On Local Search and Placement of Meters in Networks
• On miniaturized problems in parameterized complexity theory
• On problems without polynomial kernels
• On the Hardness of Losing Weight
• 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
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Stable assignment with couples: parameterized complexity and local search
• Stochastic local search. Foundations and applications.
• The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
• Which problems have strongly exponential complexity?

Cited in

(18)

• Worst-case study of local search for MAX-\(k\)-SAT.
• Local search for string problems: brute-force is essentially optimal
• Minimizing Rosenthal potential in multicast games
• Analysis of local search landscapes for \(k\)-SAT instances
• On the parallel parameterized complexity of MaxSAT variants
• On the complexity of restoring corrupted colorings
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• 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
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental Evaluation
• The parameterized complexity of local search for TSP, more refined
• Fast local search methods for solving limited memory influence diagrams
• Complexity and approximability of parameterized MAX-CSPs
• Searching for better fill-in
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Local search: is brute-force avoidable?
• The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT

This page was built for publication: The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456705)