Binarisation for Valued Constraint Satisfaction Problems

DOI10.1137/16M1088107zbMath1477.68121arXiv1608.01628OpenAlexW3098032020MaRDI QIDQ5371026

No author found.

Publication date: 24 October 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.01628

zbMATH Keywords

discrete optimizationpolymorphismsvalued constraint satisfaction problemsfractional polymorphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ Galois connections for patterns: an algebra of labelled graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maltsev digraphs have a majority polymorphism
• The expressive power of valued constraints: Hierarchies and collapses
• The expressive power of binary submodular functions
• Bounded width problems and algebras
• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• Tree clustering for constraint networks
• Binary vs. non-binary constraints
• The wonderland of reflections
• Networks of constraints: Fundamental properties and applications to picture processing
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On digraph coloring problems and treewidth duality
• A dichotomy for minimum cost graph homomorphisms
• Robustly Solvable Constraint Satisfaction Problems
• Complexity of conservative constraint satisfaction problems
• Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Skew Bisubmodularity and Valued CSPs
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A Galois Connection for Valued Constraint Languages of Infinite Size
• Algebraic Properties of Valued Constraint Satisfaction Problem
• A finer reduction of constraint problems to digraphs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Extensions of the Minimum Cost Homomorphism Problem
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Graphs of relational structures
• Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
• The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs
• The Complexity of Valued CSPs
• The Power of Linear Programming for General-Valued CSPs
• The Complexity of 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
• An Algebraic Theory of Complexity for Discrete Optimization
• The complexity of satisfiability problems
• A Simple Algorithm for Mal'tsev Constraints

This page was built for publication: Binarisation for Valued Constraint Satisfaction Problems