Modularity-based decompositions for valued CSP

DOI10.1007/S10472-013-9351-0MaRDI QIDQ353312zbMATH OpenOpenAlexFDO

Authors Maher Helaoui, Wady Naanaa

Publication date 12 July 2013

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10472-013-9351-0

zbMATH Keywords

combinatorial problemsbinary valued CSPsmodular valuation functionsproblem decomposition schemetractable subproblem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Recommendations

• A submodular-based decomposition strategy for valued CSPs
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Skew bisubmodularity and valued CSPs
• The complexity of valued CSPs
• Skew bisubmodularity and valued CSPs

Cites work

• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 2243365 (Why is no real title available?)
• A domain decomposition algorithm for constraint satisfaction
• A unified theory of structural tractability for constraint satisfaction problems
• Arc consistency for soft constraints
• Complexity classifications of Boolean constraint satisfaction problems
• Consistency in networks of relations
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• High-order consistency in valued constraint satisfaction
• Pseudo-Boolean optimization
• Radio link frequency assignment
• Reduction operations in fuzzy or valued constraint satisfaction
• Soft arc consistency revisited
• The Effect of Constraint Representation on Structural Tractability
• Tractable triangles and cross-free convexity in discrete optimisation

Cited in

(2)

• A submodular-based decomposition strategy for valued CSPs
• Bounded backtracking for the valued constraint satisfaction problems

Describes a project that uses

Uses Software

• ToulBar2

This page was built for publication: Modularity-based decompositions for valued CSP

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