Hybrid tractability of valued constraint problems

DOI10.1016/j.artint.2011.02.003zbMath1225.68243arXiv1008.4071MaRDI 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 complexity; graphical models; tractability; forbidden substructures; soft constraints; valued constraint satisfaction problems; constraint optimisation

Mathematics Subject Classification ID

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

Related Items

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