Published: March 26, 2011

**Keywords:**approximation algorithms, metric spaces, decomposition

**ACM Classification:**F.2.2

**AMS Classification:**68Q17, 68W25, 90C59

**Abstract:**
[Plain Text Version]

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.