Hybrid tractability of valued constraint problems
From MaRDI portal
Publication:646503
DOI10.1016/j.artint.2011.02.003zbMath1225.68243arXiv1008.4071MaRDI QIDQ646503
Martin C. Cooper, Stanislav Živný
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
computational complexity; graphical models; tractability; forbidden substructures; soft constraints; valued constraint satisfaction problems; constraint optimisation
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, Tractability in constraint satisfaction problems: a survey, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Discrete convexity in joint winner property, The quadratic M-convexity testing problem, 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
- 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
- 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
