  Motivated by recent work in computational social choice, we extend the metric
distortion framework to clustering problems. Given a set of $n$ agents located
in an underlying metric space, our goal is to partition them into $k$ clusters,
optimizing some social cost objective. The metric space is defined by a
distance function $d$ between the agent locations. Information about $d$ is
available only implicitly via $n$ rankings, through which each agent ranks all
other agents in terms of their distance from her. Still, we would like to
evaluate clustering algorithms in terms of social cost objectives that are
defined using $d$. This is done using the notion of distortion, which measures
how far from optimality a clustering can be, taking into account all underlying
metrics that are consistent with the ordinal information available.
Unfortunately, the most important clustering objectives do not admit algorithms
with finite distortion. To sidestep this disappointing fact, we follow two
alternative approaches: We first explore whether resource augmentation can be
beneficial. We consider algorithms that use more than $k$ clusters but compare
their social cost to that of the optimal $k$-clusterings. We show that using
exponentially (in terms of $k$) many clusters, we can get low (constant or
logarithmic) distortion for the $k$-center and $k$-median objectives.
Interestingly, such an exponential blowup is shown to be necessary. More
importantly, we explore whether limited cardinal information can be used to
obtain better results. Somewhat surprisingly, for $k$-median and $k$-center, we
show that a number of queries that is polynomial in $k$ and only logarithmic in
$n$ (i.e., only sublinear in the number of agents for the most relevant
scenarios in practice) is enough to get constant distortion.
