PTAS for MAP Assignment on Pairwise Markov Random Fields in Planar Graphs

Eli Fox-Epstein, Roie Levin, David Meierfrankenfeld

We present a PTAS for computing the maximum a posteriori assignment on Pairwise Markov Random Fields with non-negative weights in planar graphs. This algorithm is practical and not…