The complexity of valued CSPs

DOI10.4230/DFU.VOL7.15301.233zbMATH Open1482.68165OpenAlexW2593708414MaRDI QIDQ4993602FDOQ4993602

Andrei Krokhin, S. Zivny

Publication date: 15 June 2021

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

Recommendations

• The complexity of valued constraint satisfaction
• The complexity of general-valued CSPs
• An Algebraic Approach to Valued Constraint Satisfaction
• The complexity of conservative valued CSPs
• The complexity of conservative valued CSPs

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)

Cites Work

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

Cited In (12)

• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• On Planar Valued CSPs
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• The Complexity of General-Valued CSPs
• Binarisation for Valued Constraint Satisfaction Problems
• Tractability of explaining classifier decisions
• High-order consistency in valued constraint satisfaction
• The Complexity of Boolean Surjective General-Valued CSPs
• The Complexity of Boolean Surjective General-Valued CSPs
• Towards a characterization of constant-factor approximable finite-valued CSPs
• On planar valued CSPs
• An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains

Uses Software

• JBool

This page was built for publication: The complexity of valued CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993602)