The Approximability of Constraint Satisfaction Problems
From MaRDI portal
Publication:2706139
DOI10.1137/S0097539799349948zbMath0992.68059MaRDI QIDQ2706139
Sanjeev Khanna, Luca Trevisan, Madhu Sudan, David P. Williamson
Publication date: 19 March 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
approximation algorithms; hardness of approximation; approximation classes; complete problems; approximation-preserving reductions; Boolean constraint satisfaction problems
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Bounded Tree-Width and CSP-Related Problems, Minimum Cost Homomorphisms to Reflexive Digraphs, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Introduction to the Maximum Solution Problem, On the Boolean connectivity problem for Horn relations, Hard constraint satisfaction problems have hard gaps at location 1, Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, Approximability of clausal constraints, A note on some collapse results of valued constraints, Resolution for Max-SAT, The approximability of non-Boolean satisfiability problems and restricted integer programming, The complexity of Boolean constraint satisfaction local search problems, On the Hamming distance of constraint satisfaction problems., The complexity of minimal satisfiability problems, Isomorphic implication, Supermodular functions and the complexity of MAX CSP, A dichotomy for minimum cost graph homomorphisms, Linear-programming design and analysis of fast algorithms for Max 2-CSP, Approximation of the quadratic set covering problem, The complexity of soft constraint satisfaction, Constraint Satisfaction Parameterized by Solution Size, Approximability of the Maximum Solution Problem for Certain Families of Algebras, Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint, Two Edge Modification Problems without Polynomial Kernels
