Theory of Computing
-------------------
Title : Metric Clustering via Consistent Labeling
Authors : Robert Krauthgamer and Tim Roughgarden
Volume : 7
Number : 5
Pages : 49-74
URL : http://www.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.