## Rounding-based Moves for Semi-Metric Labeling

*M. Pawan Kumar, Puneet K. Dokania*; 17(91):1−42, 2016.

### Abstract

Semi-metric labeling is a special case of energy minimization
for pairwise Markov random fields. The energy function consists
of arbitrary unary potentials, and pairwise potentials that are
proportional to a given semi-metric distance function over the
label set. Popular methods for solving semi-metric labeling
include (i) move-making algorithms, which iteratively solve a
minimum $st$-cut problem; and (ii) the linear programming ( LP)
relaxation based approach. In order to convert the fractional
solution of the LP relaxation to an integer solution, several
randomized rounding procedures have been developed in the
literature. We consider a large class of parallel rounding
procedures, and design move-making algorithms that closely mimic
them. We prove that the multiplicative bound of a move-making
algorithm exactly matches the approximation factor of the
corresponding rounding procedure for any arbitrary distance
function. Our analysis includes all known results for move-
making algorithms as special cases.

[abs][pdf][bib]