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.