Theory of Computing ------------------- Title : Metric Clustering via Consistent Labeling Authors : Robert Krauthgamer and Tim Roughgarden Volume : 7 Number : 5 Pages : 49-74 URL : https://theoryofcomputing.org/articles/v007a005 Abstract -------- We design approximation algorithms for a number of fundamental optimization problems in metric spaces, namely computing separating and padded decompositions, sparse covers, and metric triangulations. Our work is the first to emphasize *relative guarantees* that compare the produced solution to the optimal one for the input at hand. By contrast, the extensive previous work on these topics has sought *absolute* bounds that hold for every possible metric space (or for a family of metrics). While absolute bounds typically translate to relative ones, our algorithms provide significantly better relative guarantees, using a rather different algorithm. Our technical approach is to cast a number of metric clustering problems that have been well studied---but almost always as disparate problems---into a common modeling and algorithmic framework, which we call the *consistent labeling* problem. Having identified the common features of all of these problems, we provide a family of linear programming relaxations and simple randomized rounding procedures that achieve provably good approximation guarantees.