The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
type: Item
instance of: scholarly article
title: The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
zbMATH Open document ID: 1248.90067
author: Stefan Szeider
published in: Discrete Optimization
publication date: 2012-10-16T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 6094039
zbMATH Keywords: parameterized complexity
zbMATH Keywords: local search
zbMATH Keywords: maximum satisfiability
MaRDI profile type: Publication
full work available at URL: j.disopt.2010.07.003
OpenAlex ID: W2017619848
cites work: Q5472387
cites work: On miniaturized problems in parameterized complexity theory
cites work: Q5710169
cites work: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
cites work: Analyses on the 2 and 3-flip neighborhoods for the MAX SAT
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Local search: is brute-force avoidable?
cites work: On Local Search and Placement of Meters in Networks
cites work: On the Hardness of Losing Weight
cites work: Searching the \(k\)-change neighborhood for TSP is W[1]-hard
cites work: Parameterized complexity and local search approaches for the stable marriage problem with ties
cites work: Stable Assignment with Couples: Parameterized Complexity and Local Search
cites work: Which problems have strongly exponential complexity?
cites work: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
cites work: A simplified NP-complete satisfiability problem
cites work: A simplified NP-complete MAXSAT problem
cites work: The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
cites work: Deciding first-order properties of locally tree-decomposable structures
cites work: On problems without polynomial kernels
DOI: 10.1016/J.DISOPT.2010.07.003
description: scientific article; zbMATH DE number 6094039