Sufficient and necessary conditions for solution finding in valuation-based systems
From MaRDI portal
Publication:2302788
Abstract: Valuation algebras abstract a large number of formalisms for automated reasoning and enable the definition of generic inference procedures. Many of these formalisms provide some notion of solution. Typical examples are satisfying assignments in constraint systems, models in logics or solutions to linear equation systems. Many widely used dynamic programming algorithms for optimization problems rely on low treewidth decompositions and can be understood as particular cases of a single algorithmic scheme for finding solutions in a valuation algebra. The most encompassing description of this algorithmic scheme to date has been proposed by Pouly and Kohlas together with sufficient conditions for its correctness. Unfortunately, the formalization relies on a theorem for which we provide counterexamples. In spite of that, the mainline of Pouly and Kohlas' theory is correct, although some of the necessary conditions have to be revised. In this paper we analyze the impact that the counter-examples have on the theory, and rebuild the theory providing correct sufficient conditions for the algorithms. Furthermore, we also provide necessary conditions for the algorithms, allowing for a sharper characterization of when the algorithmic scheme can be applied.
Recommendations
- A solution configuration and its algorithm of valuation algebras induced by a constraint semiring
- An algorithm for finding most likely explanations in valuation based systems
- Semiring induced valuation algebras: exact and approximate local computation algorithms
- On conditions for mappings to preserve optimal solutions of semiring-induced valuation algebras
- Consistency in Valuation-Based Systems
Cites work
- scientific article; zbMATH DE number 3126094 (Why is no real title available?)
- scientific article; zbMATH DE number 3174053 (Why is no real title available?)
- scientific article; zbMATH DE number 5152598 (Why is no real title available?)
- scientific article; zbMATH DE number 977284 (Why is no real title available?)
- scientific article; zbMATH DE number 1945067 (Why is no real title available?)
- scientific article; zbMATH DE number 1946853 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- A common schema for dynamic programming and branch and bound algorithms
- A stronger model of dynamic programming algorithms
- AND/OR branch-and-bound search for combinatorial optimization in graphical models
- AND/OR search spaces for graphical models
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Bridging the algorithm gap: A linear-time functional program for paragraph formatting
- Bucket elimination: A unifying framework for reasoning
- Coalition structure generation over graphs
- Compiling CSPs into tree-driven automata for interactive solving
- Composition Principles for Synthesis of Optimal Multistage Processes
- Computing all-pairs shortest paths by leveraging low treewidth
- Decomposable negation normal form
- Direct Methods for Sparse Linear Systems
- Dynamic Programming
- Dynamic programming. A computational tool.
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
- Finite-State Processes and Dynamic Programming
- Generic inference. A unifying theory for automated reasoning
- Generic local computation
- Graph theory
- Graphs, dioids and semirings. New models and algorithms.
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- Join-graph propagation algorithms
- Limitations of incremental dynamic programming
- Linear and combinatorial optimization in ordered algebraic structures
- Memory intensive AND/OR search for combinatorial optimization in graphical models
- Mini-buckets: a general scheme for bounded inference
- Non-Serial Dynamic Programming — A Survey
- Nonserial dynamic programming
- Numerical methods in matrix computations
- Probabilistic Networks and Expert Systems
- Probabilistic graphical models.
- Semiring induced valuation algebras: exact and approximate local computation algorithms
Cited in
(4)- Removing partial inconsistency in valuation-based systems
- An algorithm for finding most likely explanations in valuation based systems
- A solution configuration and its algorithm of valuation algebras induced by a constraint semiring
- scientific article; zbMATH DE number 19878 (Why is no real title available?)
This page was built for publication: Sufficient and necessary conditions for solution finding in valuation-based systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302788)
