I will talk about two recently proposed MRF optimization techniques,
whose theoretical setting rests on the duality theory of linear programming.
They both rely on the same linear programming relaxation, but they make use
of it in a different manner.
The first one is based on the so called primal-dual schema, which is a
very powerful technique for deriving approximation algorithms to NP-hard
combinatorial problems. When applied to the problem of MRF optimization,
this schema leads to graph-cut based algorithms that are
very efficient and also capable of approximately optimizing a wide variety
of MRFs.
On the other hand, the second technique is based on the principle of dual
decomposition, i.e., on one of the most powerful and widely used techniques
in optimization. When applied to the MRF problem, this technique leads to
a very flexible and general theoretical framework, whose algorithms rely on
message-passing and enjoy stronger theoretical properties compared to the
state-of-the-art.
Copyright. All Rights Reserved.