The Complexity of Valued CSPs
From MaRDI portal
Publication:4993602
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
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
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
