Towards a characterization of constant-factor approximable finite-valued CSPs
From MaRDI portal
Publication:1671996
DOI10.1016/j.jcss.2018.03.003zbMath1398.68666arXiv1610.01019OpenAlexW2962988009MaRDI QIDQ1671996
Rajsekar Manokaran, Victor Dalmau, Andrei A. Krokhin
Publication date: 7 September 2018
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.01019
Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of approximating CSP with balance/hard constraints
- A new line of attack on the dichotomy conjecture
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Characterizations of several Maltsev conditions.
- Complexity of constraints. An overview of current research themes
- The complexity of soft constraint satisfaction
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Robustly Solvable Constraint Satisfaction Problems
- On algebras with many symmetric operations
- Linear programming, width-1 CSPs, and robust satisfaction
- Robust Satisfiability for CSPs
- Near Unanimity Constraints Have Bounded Pathwidth Duality
- Approximation Algorithms and Semidefinite Programming
- Two new homomorphism dualities and lattice operations
- The Complexity of Finite-Valued CSPs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- The approximability of MAX CSP with fixed-value constraints
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Asking the Metaquestions in Constraint Tractability
- The Complexity of Valued CSPs
- Approximation Algorithms for CSPs
- How to Round Any CSP
- The Power of Linear Programming for General-Valued CSPs
- A characterization of strong approximation resistance
- The Complexity of General-Valued CSPs
- Classifying the Complexity of Constraints Using Finite Algebras
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Computational Complexity
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- An Algebraic Theory of Complexity for Discrete Optimization
- The complexity of satisfiability problems
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
- The PCP theorem by gap amplification
- Every 2-CSP allows nontrivial approximation
This page was built for publication: Towards a characterization of constant-factor approximable finite-valued CSPs
