The Complexity of Finite-Valued CSPs

From MaRDI portal
Publication:3177814

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




Related Items (41)

Tractability in constraint satisfaction problems: a surveyCLAP: A New Algorithm for Promise CSPsThe Complexity of General-Valued CSPsA Galois Connection for Valued Constraint Languages of Infinite SizeAlgebraic Properties of Valued Constraint Satisfaction ProblemSherali-Adams Relaxations for Valued CSPsNecessary Conditions for Tractability of Valued CSPsThe lattice and semigroup structure of multipermutationsOn planar valued CSPsMinimizing submodular functions on diamonds via generalized fractional matroid matchingsUniversal qudit HamiltoniansTowards a characterization of constant-factor approximable finite-valued CSPsPromise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean DichotomyAn application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domainsThe Power of Sherali--Adams Relaxations for General-Valued CSPsSuper-reparametrizations of weighted CSPs: properties and optimization perspectiveUnnamed ItemTractability of explaining classifier decisionsUnnamed ItemBinarisation for Valued Constraint Satisfaction ProblemsUsing a Min-Cut generalisation to go beyond Boolean surjective VCSPsHybrid Tractable Classes of Constraint ProblemsThe Complexity of Valued CSPsBackdoor Sets for CSP.Minimum Violation Vertex Maps and Their Applications to Cut ProblemsRepresenting Fitness Landscapes by Valued Constraints to Understand the Complexity of Local SearchStreaming Complexity of Approximating Max 2CSP and Max Acyclic SubgraphUnnamed ItemUnnamed ItemUnnamed ItemUnnamed ItemUnnamed ItemDiscrete Convex Functions on Graphs and Their Algorithmic ApplicationsDiscrete convexity and polynomial solvability in minimum 0-extension problemsRobust Algorithms with Polynomial Loss for Near-Unanimity CSPsMinimum 0-extension problems on directed metricsHalf-integrality, LP-branching, and FPT AlgorithmsTesting the Complexity of a Valued CSP LanguageConstant-Query Testability of Assignments to Constraint Satisfaction ProblemsThe Power of Linear Programming for General-Valued CSPsThe Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side




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