An LP Formulation and Approximation Algorithms for the Metric Labeling Problem
Chandra Chekuri, Sanjeev Khanna, Joseph Seffi Naor, Leonid Zosin · 2004
We consider approximation algorithms for the metric labeling problem. This problem was introduced in a paper by Kleinberg and Tardos [26], and captures many classification problems that arise in computer vision and related fields. They gave an O(log k log log k)approximation for the general case where k is the number of labels, and a2-approximation for the uniform metric case. (In fact, the bound for general metrics can be improved to O(log k)by the work of Fakcheroenphol, Rao, and Talwar [16].) Subsequently, Gupta and Tardos [18] gave a4-approximation for the truncated linear metric, a metric motivated by practical applications to image restoration and visual correspondence. In this paper we introduce an integer programming formulation and show that the integrality gap of its linear relaxation either matches or improves the ratios known for several cases of the metric labeling problem studied until now, providing a unified approach to solving them. In particular, we show that the integrality gap of our LP is bounded by O(log k)for a generalk-point metric and2for the uniform metric thus matching the known ratios. We also develop an algorithm based on our LP that achieves a ratio of 2+p2'3:414for the truncated linear metric improving the earlier known ratio of4. Our algorithm uses the fact that the integrality gap of the LP is1on a linear metric.