  There has been a long-standing interest in computing diverse solutions to
optimization problems. Motivated by reallocation of governmental institutions
in Sweden, in 1995 J. Krarup posed the problem of finding $k$ edge-disjoint
Hamiltonian Circuits of minimum total weight, called the peripatetic salesman
problem (PSP). Since then researchers have investigated the complexity of
finding diverse solutions to spanning trees, paths, vertex covers, matchings,
and more. Unlike the PSP that has a constraint on the total weight of the
solutions, recent work has involved finding diverse solutions that are all
optimal.
  However, sometimes the space of exact solutions may be too small to achieve
sufficient diversity. Motivated by this, we initiate the study of obtaining
sufficiently-diverse, yet approximately-optimal solutions to optimization
problems. Formally, given an integer $k$, an approximation factor $c$, and an
instance $I$ of an optimization problem, we aim to obtain a set of $k$
solutions to $I$ that a) are all $c$ approximately-optimal for $I$ and b)
maximize the diversity of the $k$ solutions. Finding such solutions, therefore,
requires a better understanding of the global landscape of the optimization
function.
  We show that, given any metric on the space of solutions, and the diversity
measure as the sum of pairwise distances between solutions, this problem can be
solved by combining ideas from dispersion and multicriteria optimization. We
first provide a general reduction to an associated budget-constrained
optimization (BCO) problem, where one objective function is to be maximized
(minimized) subject to a bound on the second objective function. We then prove
that bi-approximations to the BCO can be used to give bi-approximations to the
diverse approximately optimal solutions problem with a little overhead.
