De Campos, Cassio Polpo (2013) NP-hardness of MAP in Ternary Tree Bayesian Networks. Technical Report UNSPECIFIED
Text
IDSIA-06-13.pdf Download (270kB) |
Official Website: http://www.idsia.ch/~cassio/publist/papers/IDSIA-0...
Abstract
This paper strengthens the NP-hardness result for the (partial) maximum a posteriori (MAP) problem in Bayesian networks with topology of trees (every variable has at most one parent) and variable cardinality at most three. MAP is the problem of querying the most probable state configuration of some (not necessarily all) of the network variables given evidence. It is demonstrated that the problem remains hard even in such simplistic networks.
Item Type: | Report (Technical Report) |
---|---|
Additional Information: | No. IDSIA-06-13 |
Subjects: | Computer sciences |
Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull’intelligenza artificiale USI-SUPSI |
Depositing User: | Cassio Polpo De Campos |
Date Deposited: | 13 Mar 2014 14:16 |
Last Modified: | 16 Sep 2014 05:40 |
URI: | http://repository.supsi.ch/id/eprint/3906 |
Actions (login required)
View Item |