Approximating MAPs for Belief Networks is NP-Hard and Other Theorems

By A. Abdelbar, S. M. Hedetniemi. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Lise Getoor
2. B. Taskar
3. Alex Kulesza
4. Stephen H. Bach
5. Bert Huang
6. Matthias Broecheler
7. Yoshua Bengio
8. Ruslan Salakhutdinov

Citations in the corpus

• Determinantal Point Processes for Machine Learning (2012, background): “Shimony [130] proved that the MAP inference problem (finding the mode of an MRF) is also NP-hard, and Abdelbar and Hedetniemi [1] showed that the MAP problem is likewise hard to approximate.”
• Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, background): “This is to be expected, since even approximating MAP is NP-hard in general (Abdelbar and Hedetniemi, 1998).”