The Complexity of Valued CSPs

DOI10.4230/DFU.Vol7.15301.233zbMath1482.68165OpenAlexW2593708414MaRDI QIDQ4993602

Andrei A. Krokhin, Stanislav Živný

Publication date: 15 June 2021

Full work available at URL: https://doi.org/10.4230/DFU.Vol7.15301.9

zbMATH Keywords

optimisationconstraint satisfaction problemstractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Related Items

The Complexity of General-Valued CSPs ⋮ On planar valued CSPs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Tractability of explaining classifier decisions ⋮ Binarisation for Valued Constraint Satisfaction Problems

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring, constraint satisfaction, and complexity
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Hybrid tractability of valued constraint problems
• On the complexity of submodular function minimisation on diamonds
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• The expressive power of binary submodular functions
• Structural properties of oracle classes
• Submodular function minimization
• Bounded width problems and algebras
• Existence theorems for weakly symmetric operations
• Universal algebra and hardness results for constraint satisfaction problems
• Geometric algorithms and combinatorial optimization
• Polynomial combinatorial algorithms for skew-bisubmodular function minimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• Characterizations of several Maltsev conditions.
• Complexity of constraints. An overview of current research themes
• Supermodular functions and the complexity of MAX CSP
• A dichotomy for minimum cost graph homomorphisms
• The complexity of soft constraint satisfaction
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Submodular functions and optimization.
• The Approximability of Constraint Satisfaction Problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
• Half-integrality, LP-branching, and FPT Algorithms
• The collapse of the bounded width hierarchy
• Linear programming, width-1 CSPs, and robust satisfaction
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
• Complexity of conservative constraint satisfaction problems
• Robust Satisfiability for CSPs
• Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains
• Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• Towards Minimizing k-Submodular Functions
• Min CSP on Four Elements: Moving beyond Submodularity
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Skew Bisubmodularity and Valued CSPs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Sherali-Adams Relaxations for Valued CSPs
• The approximability of MAX CSP with fixed-value constraints
• Necessary Conditions for Tractability of Valued CSPs
• A finer reduction of constraint problems to digraphs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Extensions of the Minimum Cost Homomorphism Problem
• Graphical Models, Exponential Families, and Variational Inference
• Information, Physics, and Computation
• MAX ONES Generalized to Larger Domains
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
• A new approach to the maximum-flow problem
• On the Structure of Polynomial Time Reducibility
• Varieties Obeying Homotopy Laws
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Complexity of Multiterminal Cuts
• Closure properties of constraints
• Correlation Decay and Tractability of CSPs.
• Fixed-parameter Approximability of Boolean MinCSPs
• Weak consistency notions for all the CSPs of bounded width
• Graphs of relational structures
• The Complexity of Valued Constraint Satisfaction Problems
• The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• Constraint Satisfaction Problems over Numeric Domains
• Hybrid Tractable Classes of Constraint Problems
• Algebra and the Complexity of Digraph CSPs: a Survey
• Approximation Algorithms for CSPs
• Oracle Tractability of Skew Bisubmodular Functions
• 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
• Robust satisfiability of constraint satisfaction problems
• The Approximability of Three-valued MAX CSP
• A Simple Algorithm for Mal'tsev Constraints
• Bisubmodular Function Minimization
• Basics of Galois Connections
• Introduction to the Maximum Solution Problem
• Discrete convexity and polynomial solvability in minimum 0-extension problems

This page was built for publication: The Complexity of Valued CSPs