Rounding-based Moves for Metric Labeling
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 metric distance function over the label set. Popular methods for solving 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.
The authors analyze the relationship between randomized roundingalgorithms and move-making algorithms for metriclabeling, which is the problem of MAP inference in a MRF where thebinary potentials are proportional to a distance metric on the labelspace. They demonstrate connections between the two classes ofalgorithms. For each of three rounding schemes---complete, interval,and hierarchical---they present companion move-making algorithms thatachieve the same worst-case approximation ratio (over all possibleunary potentials and edge weights) for any particular distance metricon the label space.The primary contribution of the paper is the analysis, which showsthat the move-making algorithms have the same approximation guaranteesas the rounding-based ones. This is significant because therounding-based algorithms have historically come with the strongestapproximation guarantees, but move-making algorithms are faster. Thus,the guarantees are exported to the faster algorithms.The paper can be situated slightly better in terms of prior work. Fromwhat I can tell:* Previous papers [14,15] have presented move-making algorithms  similar to those given here and proved approximation factors for  those algorithms for certain classes of distance functions. * This work, on the other hand, applies to *any* distance function,  and shows that the approximation ratio of the rounding scheme  (for that distance function) is matched by the companion move-making  algorithm. The difference between this and previous results is  subtle and could be emphasized more.* I believe the move-making algorithms themselves are not  contributions of this paper. It would help a great deal if the  authors could clearly attribute each algorithm to a particular  source and describe which parts are their original contributions. The paper is well-written and generally well executed. I felt that toomuch of the paper was used describing the algorithms in detailgiven that the main intellectual contribution seems to be in theanalysis.A significant question that is left unanswered in the main paper is:what is the general analysis technique for converting a roundingscheme to a move-making algorithm? Is there a clear recipe? If not,what are the significant elements of the analysis? The paper would bestrengthened considerably by providing some discussion of this.