  We describe the first strongly subquadratic time algorithm with
subexponential approximation ratio for approximately computing the Fr\'echet
distance between two polygonal chains. Specifically, let $P$ and $Q$ be two
polygonal chains with $n$ vertices in $d$-dimensional Euclidean space, and let
$\alpha \in [\sqrt{n}, n]$. Our algorithm deterministically finds an
$O(\alpha)$-approximate Fr\'echet correspondence in time $O((n^3 / \alpha^2)
\log n)$. In particular, we get an $O(n)$-approximation in near-linear $O(n
\log n)$ time, a vast improvement over the previously best know result, a
linear time $2^{O(n)}$-approximation. As part of our algorithm, we also
describe how to turn any approximate decision procedure for the Fr\'echet
distance into an approximate optimization algorithm whose approximation ratio
is the same up to arbitrarily small constant factors. The transformation into
an approximate optimization algorithm increases the running time of the
decision procedure by only an $O(\log n)$ factor.
