Hybrid tractability of valued constraint problems

DOI10.1016/j.artint.2011.02.003zbMath1225.68243arXiv1008.4071OpenAlexW2146944439MaRDI QIDQ646503

Stanislav Živný, Martin C. Cooper

Publication date: 17 November 2011

Published in: Artificial Intelligence (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraphical modelstractabilityforbidden substructuressoft constraintsvalued constraint satisfaction problemsconstraint optimisation

Mathematics Subject Classification ID

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

Related Items (17)

Tractability in constraint satisfaction problems: a survey ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Discrete convexity in joint winner property ⋮ Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ Tractability of explaining classifier decisions ⋮ The quadratic M-convexity testing problem ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ The Broken-Triangle Property with Adjoint Values ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ A Tractable Class of Binary VCSPs via M-Convex Intersection ⋮ Unnamed Item ⋮ Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
• Network-based heuristics for constraint-satisfaction problems
• The ellipsoid method and its consequences in combinatorial optimization
• On the algebraic structure of combinatorial problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cost-based arc consistency for global cardinality constraints
• The complexity of soft constraint satisfaction
• Recognizing Berge graphs
• On global warming: Flow-based soft global constraints
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• Generalizing AllDifferent: The SomeDifferent Constraint
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Graphical Models, Exponential Families, and Variational Inference
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Semiring-based constraint satisfaction and optimization
• Scheduling independent tasks to reduce mean finishing time
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of conservative valued CSPs
• The complexity of satisfiability problems
• Technical Note—Minimizing Average Flow Time with Parallel Machines
• Independent Sets of Maximum Weight in Apple-Free Graphs
• Principles and Practice of Constraint Programming – CP 2003
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Hybrid tractability of valued constraint problems