0
$\begingroup$

Approximating Discrete Markov Random Field (MRF) is also called Discrete Markov Random Field Relaxation in literature.

A 3 values 4 variables MRF can be defined as $$\sum_{a_1=0}^{2}\sum_{a_2=0}^{2}\sum_{a_3=0}^{2}\sum_{a_4=0}^{2} H(a_1,a_2)H(a_1,a_3)H(a_1,a_4)H(a_2,a_3)H(a_2,a_4)H(a_3,a_4)>0$$

There are many different strategies, e.g. Belief Propagation, Linear Programming approximation.

What are your ways to approximate MRF?

[Problem Source: Discrete Markov Random Field Relaxation][1] [1]: https://www.slideshare.net/SingKuangTan/discrete-markov-random-field-relaxation

$\endgroup$