Complexity and approximability of parameterized MAX-CSPs
From MaRDI portal
Publication:2408203
DOI10.1007/s00453-017-0310-8zbMath1372.68121OpenAlexW2245328064MaRDI QIDQ2408203
Valia Mitsou, Michael Lampis, Tobias Mömke, Holger Dell, Eun Jung Kim
Publication date: 10 October 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5591/
approximationconstraint satisfaction problemsparameterized complexityneighborhood diversityclique width
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Satisfiability of acyclic and almost acyclic CNF formulas
- Satisfiability, branch-width and Tseitin tautologies
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- Constraint satisfaction with bounded treewidth revisited
- A dichotomy theorem for maximum generalized satisfiability problems.
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Algorithmic meta-theorems for restrictions of treewidth
- Linear time solvable optimization problems on graphs of bounded clique-width
- Backdoors to Acyclic SAT
- Model Counting for Formulas of Bounded Clique-Width
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Model Counting for CNF Formulas of Bounded Modular Treewidth
- A characterization of approximation resistance for even k-partite CSPs
- Integer Programming with a Fixed Number of Variables
- Solving MaxSAT and #SAT on Structured CNF Formulas
- Approximating CSPs Using LP Relaxation
- Hardness of Learning Halfspaces with Noise
- Agnostic Learning of Monomials by Halfspaces Is Hard
- Theory and Applications of Satisfiability Testing
- Tractable answer-set programming with weight constraints: bounded treewidth is not enough
- Some optimal inapproximability results
- Majority is stablest
- The Structure of Tractable Constraint Satisfaction Problems
