The complexity of conservative valued CSPs
From MaRDI portal
Publication:5395709
DOI10.1145/2450142.2450146zbMath1281.68134arXiv1110.2809OpenAlexW2034122136MaRDI QIDQ5395709
Stanislav Živný, Vladimir Kolmogorov
Publication date: 17 February 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.2809
complexitysubmodularitydiscrete optimizationdichotomyvalued constraint satisfaction problemsmultimorphisms
Related Items
Tractability in constraint satisfaction problems: a survey ⋮ The Complexity of General-Valued CSPs ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ On planar valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ A complexity classification of spin systems with an external field ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Hybrid tractability of valued constraint problems ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ Backdoor Sets for CSP. ⋮ Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ The complexity of approximating conservative counting CSPs ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ Unnamed Item ⋮ The Power of Linear Programming for General-Valued CSPs
This page was built for publication: The complexity of conservative valued CSPs
