  Given a finite metric space $(V,d)$, an approximate distance oracle is a data
structure which, when queried on two points $u,v \in V$, returns an
approximation to the the actual distance between $u$ and $v$ which is within
some bounded stretch factor of the true distance. There has been significant
work on the tradeoff between the important parameters of approximate distance
oracles (and in particular between the size, stretch, and query time), but in
this paper we take a different point of view, that of per-instance
optimization. If we are given an particular input metric space and stretch
bound, can we find the smallest possible approximate distance oracle for that
particular input? Since this question is not even well-defined, we restrict our
attention to well-known classes of approximate distance oracles, and study
whether we can optimize over those classes.
  In particular, we give an $O(\log n)$-approximation to the problem of finding
the smallest stretch $3$ Thorup-Zwick distance oracle, as well as the problem
of finding the smallest P\v{a}tra\c{s}cu-Roditty distance oracle. We also prove
a matching $\Omega(\log n)$ lower bound for both problems, and an
$\Omega(n^{\frac{1}{k}-\frac{1}{2^{k-1}}})$ integrality gap for the more
general stretch $(2k-1)$ Thorup-Zwick distance oracle. We also consider the
problem of approximating the best TZ or PR approximate distance oracle
\emph{with outliers}, and show that more advanced techniques (SDP relaxations
in particular) allow us to optimize even in the presence of outliers.
