The complexity of valued CSPs

DOI10.4230/DFU.VOL7.15301.233MaRDI QIDQ4993602zbMATH OpenOpenAlexFDO

Authors Andrei Krokhin, S. Zivny

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)

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

Cites work

• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 3972929 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1134987 (Why is no real title available?)
• scientific article; zbMATH DE number 7051294 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A Galois connection for weighted (relational) clones of infinite size
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A Simple Algorithm for Mal'tsev Constraints
• A dichotomy for minimum cost graph homomorphisms
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A dichotomy theorem for the general minimum cost homomorphism problem
• A finer reduction of constraint problems to digraphs
• A new approach to the maximum-flow problem
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• Algebra and the complexity of digraph CSPs: a survey
• Algebraic properties of valued constraint satisfaction problem
• An algebraic theory of complexity for discrete optimization.
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• Approximation Algorithms for CSPs
• Basics of Galois Connections
• Bisubmodular Function Minimization
• Bounded width problems and algebras
• Characterizations of several Maltsev conditions.
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Colouring, constraint satisfaction, and complexity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of conservative constraint satisfaction problems
• Complexity of constraints. An overview of current research themes
• Computational complexity of the extended minimum cost homomorphism problem on three-element domains
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraint satisfaction problems over numeric domains
• Correlation decay and tractability of CSPs
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Equivalence constraint satisfaction problems
• Existence theorems for weakly symmetric operations
• Extensions of the minimum cost homomorphism problem
• Fixed-parameter Approximability of Boolean MinCSPs
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• Geometric algorithms and combinatorial optimization
• Graphical models, exponential families, and variational inference
• Graphs of relational structures: restricted types
• Half-integrality, LP-branching, and FPT algorithms
• Hybrid tractability of valued constraint problems
• Hybrid tractable classes of constraint problems
• Information, Physics, and Computation
• Introduction to the Maximum Solution Problem
• Linear programming, width-1 CSPs, and robust satisfaction
• MAX ONES Generalized to Larger Domains
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• Min CSP on four elements: moving beyond submodularity
• Necessary conditions for tractability of valued CSPs
• On the Structure of Polynomial Time Reducibility
• On the complexity of submodular function minimisation on diamonds
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Oracle tractability of skew bisubmodular functions
• Polynomial combinatorial algorithms for skew-bisubmodular function minimization
• Robust satisfiability for CSPs: hardness and algorithmic results
• Robust satisfiability of constraint satisfaction problems
• Sherali-Adams relaxations for valued CSPs
• Skew bisubmodularity and valued CSPs
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• Structural properties of oracle classes
• Submodular function minimization
• Submodular functions and optimization.
• Submodularity on a tree: unifying \(L^\natural\)-convex and bisubmodular functions
• Supermodular functions and the complexity of MAX CSP
• The Approximability of Three-valued MAX CSP
• The Complexity of Multiterminal Cuts
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The approximability of MAX CSP with fixed-value constraints
• The approximability of constraint satisfaction problems
• The collapse of the bounded width hierarchy
• The complexity of conservative valued CSPs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of satisfiability problems
• The complexity of soft constraint satisfaction
• The complexity of valued constraint satisfaction
• The complexity of valued constraint satisfaction problems
• The constraint satisfaction problem and universal algebra
• The dichotomy of minimum cost homomorphism problems for digraphs
• The expressive power of binary submodular functions
• The power of Sherali-Adams relaxations for general-valued CSPs
• The power of linear programming for general-valued CSPs
• Towards minimizing \(k\)-submodular functions
• Tractability and learnability arising from algebras with few subpowers
• Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Tractable triangles and cross-free convexity in discrete optimisation
• Universal algebra and hardness results for constraint satisfaction problems
• Varieties Obeying Homotopy Laws
• Weak consistency notions for all the CSPs of bounded width

Cited in

(19)

• On Planar Valued CSPs
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• The complexity of valued constraint satisfaction
• A note on some collapse results of valued constraints
• The complexity of conservative valued CSPs
• The power of Sherali-Adams relaxations for general-valued CSPs
• Tractability of explaining classifier decisions
• The complexity of valued constraint satisfaction problems
• High-order consistency in valued constraint satisfaction
• Binarisation for valued constraint satisfaction problems
• The complexity of general-valued CSPs
• Hybrid tractable classes of constraint problems
• 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
• Modularity-based decompositions for valued CSP
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

Describes a project that uses

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)