The Complexity of General-Valued CSPs
From MaRDI portal
Publication:5283238
DOI10.1137/16M1091836zbMath1371.68117arXiv1502.07327OpenAlexW2613504727MaRDI QIDQ5283238
Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek
Publication date: 21 July 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.07327
Related Items
Tractability in constraint satisfaction problems: a survey, CLAP: A New Algorithm for Promise CSPs, Necessary Conditions for Tractability of Valued CSPs, The lattice and semigroup structure of multipermutations, Towards a characterization of constant-factor approximable finite-valued CSPs, Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection., Sparsification of Binary CSPs, The Power of Sherali--Adams Relaxations for General-Valued CSPs, PTAS for Sparse General-valued CSPs, Tractability of explaining classifier decisions, Unnamed Item, The Complexity of Boolean Surjective General-Valued CSPs, Binarisation for Valued Constraint Satisfaction Problems, Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs, Unnamed Item, Unnamed Item, Unnamed Item, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Sparsification of Binary CSPs, A Tractable Class of Binary VCSPs via M-Convex Intersection, Piecewise linear valued constraint satisfaction problems with fixed number of variables, Testing the Complexity of a Valued CSP Language, The Complexity of Quantified Constraints Using the Algebraic Formulation, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the algebraic structure of combinatorial problems
- Conjunctive-query containment and constraint satisfaction
- Networks of constraints: Fundamental properties and applications to picture processing
- Complexity of constraints. An overview of current research themes
- Supermodular functions and the complexity of MAX CSP
- The complexity of soft constraint satisfaction
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Robustly Solvable Constraint Satisfaction Problems
- The collapse of the bounded width hierarchy
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
- Complexity of conservative constraint satisfaction problems
- Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains
- A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
- Min CSP on Four Elements: Moving beyond Submodularity
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- The Complexity of Finite-Valued CSPs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Algebraic Properties of Valued Constraint Satisfaction Problem
- Sherali-Adams Relaxations for Valued CSPs
- The approximability of MAX CSP with fixed-value constraints
- Effectiveness of Structural Restrictions for Hybrid CSPs
- An Algebraic Characterisation of Complexity for Valued Constraint
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Graphical Models, Exponential Families, and Variational Inference
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Correlation Decay and Tractability of CSPs.
- A Galois Connection for Weighted (Relational) Clones of Infinite Size
- The Complexity of Valued CSPs
- The Power of Linear Programming for General-Valued CSPs
- Classifying the Complexity of Constraints Using Finite Algebras
- The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
- The Power of Sherali--Adams Relaxations for General-Valued CSPs
- Tractability and Learnability Arising from Algebras with Few Subpowers
- The complexity of conservative valued CSPs
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- An Algebraic Theory of Complexity for Discrete Optimization
- The complexity of satisfiability problems
- The Approximability of Three-valued MAX CSP
- Introduction to the Maximum Solution Problem
- Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
- Every 2-CSP allows nontrivial approximation