A dichotomy theorem for maximum generalized satisfiability problems.
From MaRDI portal
Publication:960525
DOI10.1006/jcss.1995.1087zbMath1294.68090OpenAlexW2117290960MaRDI QIDQ960525
Publication date: 21 December 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1995.1087
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Complexity versus stability for classes of propositional formulas ⋮ The complexity of minimal satisfiability problems ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Supermodular functions and the complexity of MAX CSP ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ Unnamed Item ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ On the Boolean connectivity problem for Horn relations ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Unnamed Item ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ PCPs and the hardness of generating synthetic data ⋮ Optimal satisfiability for propositional calculi and constraint satisfaction problems. ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Backdoor Sets for CSP. ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ On the complexity of submodular function minimisation on diamonds ⋮ Constant unary constraints and symmetric real-weighted counting constraint satisfaction problems ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Isomorphic implication ⋮ The complexity of Boolean constraint satisfaction local search problems ⋮ Complexity Classification of Local Hamiltonian Problems ⋮ Selecting and covering colored points ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Unnamed Item ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
