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

DOI10.1016/J.DISOPT.2010.07.003zbMATH Open1248.90067OpenAlexW2017619848MaRDI QIDQ456705FDOQ456705

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

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.

zbMATH Keywords

local searchparameterized complexitymaximum satisfiability

Mathematics Subject Classification ID

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

Cites Work

• On problems without polynomial kernels
• Which problems have strongly exponential complexity?
• Title not available (Why is that?)
• A simplified NP-complete satisfiability problem
• Stochastic local search. Foundations and applications.
• A simplified NP-complete MAXSAT problem
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Graph-Theoretic Concepts in Computer Science
• Deciding first-order properties of locally tree-decomposable structures
• On Local Search and Placement of Meters in Networks
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• Local search: is brute-force avoidable?
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• On miniaturized problems in parameterized complexity theory
• On the Hardness of Losing Weight
• Analyses on the 2 and 3-flip neighborhoods for the MAX SAT
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
• Stable assignment with couples: parameterized complexity and local search

Cited In (15)

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

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)