  We consider the bi-criteria shortest-path problem where we want to compute
shortest paths on a graph that simultaneously balance two cost functions. While
this problem has numerous applications, there is usually no path minimizing
both cost functions simultaneously. Thus, we typically consider the set of
paths where no path is strictly better then the others in both cost functions,
a set called the Pareto-optimal frontier. Unfortunately, the size of this set
may be exponential in the number of graph vertices and the general problem is
NP-hard. While existing schemes to approximate this set exist, they may be
slower than exact approaches when applied to relatively small instances and
running them on graphs with even a moderate number of nodes is often
impractical. The crux of the problem lies in how to efficiently approximate the
Pareto-optimal frontier. Our key insight is that the Pareto-optimal frontier
can be approximated using pairs of paths. This simple observation allows us to
run a best-first-search while efficiently and effectively pruning away
intermediate solutions in order to obtain an approximation of the Pareto
frontier for any given approximation factor. We compared our approach with an
adaptation of BOA*, the state-of-the-art algorithm for computing exact
solutions to the bi-criteria shortest-path problem. Our experiments show that
as the problem becomes harder, the speedup obtained becomes more pronounced.
Specifically, on large roadmaps, we obtain an average speedup of more than
$\times 8.5$ and a maximal speedup of over $\times 148$.
