Approximation algorithms for the metric labeling problem via a new linear programming formulation.

Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin

Browse the full SODA paper archive.