The complexity of valued constraint satisfaction problems

DOI10.1007/978-3-642-33974-5MaRDI QIDQ4911805zbMATH OpenOpenAlexFDO

Authors S. Zivny

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

zbMATH Keywords

constraint satisfaction problemsexpressivenesslinear programmingsubmodularitytractability

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Linear programming (90C05)

Recommendations

• The complexity of valued CSPs
• The complexity of valued constraint satisfaction
• The complexity of general-valued CSPs
• An Algebraic Approach to Valued Constraint Satisfaction
• A note on some collapse results of valued constraints

Cited in

(33)

• On a general framework for network representability in discrete optimization
• Discrete convexity in joint winner property
• Polynomial combinatorial algorithms for skew-bisubmodular function minimization
• Minimum 0-extension problems on directed metrics
• Piecewise linear valued constraint satisfaction problems with fixed number of variables
• New width parameters for SAT and \#SAT
• On planar valued CSPs
• Tractability in constraint satisfaction problems: a survey
• On \(k\)-submodular relaxation
• On a general framework for network representability in discrete optimization (extended abstract)
• Tractable triangles and cross-free convexity in discrete optimisation
• Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
• Community structure inspired algorithms for SAT and \#SAT
• Necessary conditions for tractability of valued CSPs
• The Expressive Power of Valued Constraints: Hierarchies and Collapses
• On Planar Valued CSPs
• Discrete convex functions on graphs and their algorithmic applications
• The complexity of valued constraint satisfaction
• A tractable class of binary VCSPs via M-convex intersection
• The complexity of valued CSPs
• scientific article; zbMATH DE number 7559417 (Why is no real title available?)
• An Algebraic Approach to Valued Constraint Satisfaction
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• The power of linear programming for general-valued CSPs
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• 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
• Quantaloidal approach to constraint satisfaction
• Hybrid tractability of valued constraint problems
• Valued constraint satisfaction problems
• Reconstructing sets of strings from their k-way projections: algorithms \& complexity (extended abstract)
• The expressive power of valued constraints: Hierarchies and collapses
• A note on some collapse results of valued constraints

This page was built for publication: The complexity of valued constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4911805)