Almost No News on the Complexity of MAP in Bayesian Networks
Abstract
This article discusses the current state of the art in terms of computational complexity for the problem of finding the most probable configuration of a subset of variables in a multivariate domain modelled by probabilistic graphical models such as Markov networks (random fields) or Bayesian networks. It contains complexity proofs and an algorithm for the problem and shows empirical results for Boolean trees which may suggest tractability of the task in some special cases.
Cite
Text
de Campos. "Almost No News on the Complexity of MAP in Bayesian Networks." Proceedings of pgm 2020, 2020.Markdown
[de Campos. "Almost No News on the Complexity of MAP in Bayesian Networks." Proceedings of pgm 2020, 2020.](https://mlanthology.org/pgm/2020/decampos2020pgm-almost/)BibTeX
@inproceedings{decampos2020pgm-almost,
title = {{Almost No News on the Complexity of MAP in Bayesian Networks}},
author = {de Campos, Cassio P.},
booktitle = {Proceedings of pgm 2020},
year = {2020},
pages = {149-160},
volume = {138},
url = {https://mlanthology.org/pgm/2020/decampos2020pgm-almost/}
}