M. Pawan Kumar 
HOME

ROUNDINGBASED MOVES FOR SEMIMETRIC LABELING M. Pawan Kumar and P. Dokania In Journal of Machine Learning Research (JMLR), 2016 Semimetric 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 semimetric distance function over the label set. Popular methods for solving semimetric labeling include (i) movemaking algorithms, which iteratively solve a minimum stcut 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 movemaking algorithms that closely mimic them. We prove that the multiplicative bound of a movemaking algorithm exactly matches the approximation factor of the corresponding rounding procedure for any arbitrary distance function. Our analysis includes all known results for movemaking algorithms as special cases. [Paper] 