The complexity of valued CSPs
From MaRDI portal
Publication:4993602
Recommendations
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
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)