Algebraic Properties of Valued Constraint Satisfaction Problem

DOI10.1007/978-3-662-47672-7_69zbMath1441.68098arXiv1403.0476OpenAlexW3102749561MaRDI QIDQ3448842

Joanna Ochremiak, Marcin Kozik

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

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) Computational aspects of satisfiability (68R07)

Related Items

CLAP: A New Algorithm for Promise CSPs ⋮ The Complexity of General-Valued CSPs ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ On a general framework for network representability in discrete optimization ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ On planar 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 ⋮ PTAS for Sparse General-valued CSPs ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Unnamed Item ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ The Complexity of Valued CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Piecewise linear valued constraint satisfaction problems with fixed number of variables ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

Cites Work

• Universal algebra and hardness results for constraint satisfaction problems
• On the complexity of H-coloring
• The complexity of soft constraint satisfaction
• A remark on functionally free algebras
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Complexity of conservative constraint satisfaction problems
• The Complexity of Finite-Valued CSPs
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of conservative valued CSPs
• An Algebraic Theory of Complexity for Discrete Optimization
• The complexity of satisfiability problems
• Skew Bisubmodularity and Valued CSPs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algebraic Properties of Valued Constraint Satisfaction Problem