On the constant-factor approximability of minimum cost constraint satisfaction problems
From MaRDI portal
Cites work
- A bounded approximation for the minimum cost 2-sat problem
- A Deterministic Reduction for the Gap Minimum Distance Problem
- A dichotomy for minimum cost graph homomorphisms
- A dichotomy theorem for nonuniform CSPs
- A dichotomy theorem for the general minimum cost homomorphism problem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- A new tractable class of constraint satisfaction problems
- A proof of the CSP dichotomy conjecture
- Approximation of minimum cost homomorphisms
- Characterising tractable constraints
- Closed systems of functions and predicates
- Conservative constraint satisfaction re-revisited
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Constraints, consistency and closure
- Hardness of approximating the minimum distance of a linear code
- Homogeneous operations and homogeneous algebras
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 3819803 (Why is no real title available?)
- scientific article; zbMATH DE number 3972929 (Why is no real title available?)
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- scientific article; zbMATH DE number 3336786 (Why is no real title available?)
- Inapproximability of hypergraph vertex cover and applications to scheduling problems
- Introduction to the Maximum Solution Problem
- On LP-based approximability for strict CSPs
- On the mysteries of MAX NAE-SAT
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Robust satisfiability for CSPs: hardness and algorithmic results
- Separating \textsc{max} 2-\textsc{and}, \textsc{max di}-cut and \textsc{max cut}
- The approximability of constraint satisfaction problems
- The collapse of the bounded width hierarchy
- The complexity of finite-valued CSPs
- The complexity of satisfiability problems
- The complexity of valued CSPs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The dichotomy of minimum cost homomorphism problems for digraphs
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
This page was built for publication: On the constant-factor approximability of minimum cost constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346847)
