The Complexity of Finite-Valued CSPs

DOI10.1145/2974019zbMath1410.68177arXiv1210.2987OpenAlexW2523377094MaRDI QIDQ3177814

Stanislav Živný, Johan Thapper

Publication date: 2 August 2018

Published in: Journal of the ACM, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

complexitydiscrete optimizationdichotomyvalued constraint satisfaction problemsfinite-valued constraint satisfaction problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (41)

Tractability in constraint satisfaction problems: a survey ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ The Complexity of General-Valued CSPs ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ The lattice and semigroup structure of multipermutations ⋮ On planar valued CSPs ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ Universal qudit Hamiltonians ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Super-reparametrizations of weighted CSPs: properties and optimization perspective ⋮ Unnamed Item ⋮ Tractability of explaining classifier decisions ⋮ Unnamed Item ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ Backdoor Sets for CSP. ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search ⋮ Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Minimum 0-extension problems on directed metrics ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Testing the Complexity of a Valued CSP Language ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

This page was built for publication: The Complexity of Finite-Valued CSPs