Metric labeling is an important special case of MAP estimation for pairwise
graphical models. The dominant methods for metric labeling in the computer
vision community belong to the move-making family, due to their computational
efficiency. The dominant methods in the computer science community belong to
the convex relaxations family, due to their strong theoretical guarantees. In
this talk, I will present algorithms that combine the best of both worlds:
efficient move-making algorithms that provide the same guarantees as the
standard linear programming relaxation.