The Complexity of Valued Constraint Satisfaction Problems
From MaRDI portal
Publication:4911805
DOI10.1007/978-3-642-33974-5zbMath1283.68024OpenAlexW1894390600MaRDI QIDQ4911805
Publication date: 20 March 2013
Published in: Cognitive Technologies (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-33974-5
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items (21)
Tractability in constraint satisfaction problems: a survey ⋮ On a general framework for network representability in discrete optimization ⋮ Community Structure Inspired Algorithms for SAT and #SAT ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ Discrete convexity in joint winner property ⋮ Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. ⋮ Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs ⋮ Super-reparametrizations of weighted CSPs: properties and optimization perspective ⋮ Unnamed Item ⋮ The Complexity of Valued CSPs ⋮ New width parameters for SAT and \#SAT ⋮ Unnamed Item ⋮ Polynomial combinatorial algorithms for skew-bisubmodular function minimization ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Minimum 0-extension problems on directed metrics ⋮ A Tractable Class of Binary VCSPs via M-Convex Intersection ⋮ On $k$-Submodular Relaxation ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ On a General Framework for Network Representability in Discrete Optimization ⋮ The Power of Linear Programming for General-Valued CSPs
This page was built for publication: The Complexity of Valued Constraint Satisfaction Problems
