The Approximability of Constraint Satisfaction Problems

DOI10.1137/S0097539799349948zbMath0992.68059OpenAlexW2068190866MaRDI QIDQ2706139

Luca Trevisan, Sanjeev Khanna, David P. Williamson, Madhu Sudan

Publication date: 19 March 2001

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539799349948

zbMATH Keywords

approximation algorithms hardness of approximation approximation classes complete problems approximation-preserving reductions Boolean constraint satisfaction problems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (53)

On regularity of Max-CSPs and Min-CSPs ⋮ Efficient multiple constraint acquisition ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ The complexity of minimal satisfiability problems ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Simultaneous Approximation of Constraint Satisfaction Problems ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ Complexity of approximating CSP with balance/hard constraints ⋮ Supermodular functions and the complexity of MAX CSP ⋮ Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ On the Boolean connectivity problem for Horn relations ⋮ Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints ⋮ Intractability of assembly sequencing: Unit disks in the plane ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ PTAS for Sparse General-valued CSPs ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ PCPs and the hardness of generating synthetic data ⋮ Affine reductions for LPs and SDPs ⋮ The Complexity of Valued CSPs ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Constraint Satisfaction Parameterized by Solution Size ⋮ The Next Whisky Bar ⋮ Approximability of clausal constraints ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Isomorphic implication ⋮ The complexity of Boolean constraint satisfaction local search problems ⋮ A note on some collapse results of valued constraints ⋮ Unnamed Item ⋮ Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Selecting and covering colored points ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ Approximability of the Maximum Solution Problem for Certain Families of Algebras ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ Resolution for Max-SAT ⋮ Minimal distance of propositional models ⋮ Two Edge Modification Problems without Polynomial Kernels ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Introduction to the Maximum Solution Problem ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ On the Hamming distance of constraint satisfaction problems. ⋮ Unnamed Item

This page was built for publication: The Approximability of Constraint Satisfaction Problems