  We consider the online $k$-taxi problem, a generalization of the $k$-server
problem, in which $k$ servers are located in a metric space. A sequence of
requests is revealed one by one, where each request is a pair of two points,
representing the start and destination of a travel request by a passenger. The
goal is to serve all requests while minimizing the distance traveled without
carrying a passenger.
  We show that the classic Double Coverage algorithm has competitive ratio
$2^k-1$ on HSTs, matching a recent lower bound for deterministic algorithms.
For bounded depth HSTs, the competitive ratio turns out to be much better and
we obtain tight bounds. When the depth is $d\ll k$, these bounds are
approximately $k^d/d!$. By standard embedding results, we obtain a randomized
algorithm for arbitrary $n$-point metrics with (polynomial) competitive ratio
$O(k^c\Delta^{1/c}\log_{\Delta} n)$, where $\Delta$ is the aspect ratio and
$c\ge 1$ is an arbitrary positive integer constant. The only previous known
bound was $O(2^k\log n)$. For general (weighted) tree metrics, we prove the
competitive ratio of Double Coverage to be $\Theta(k^d)$ for any fixed depth
$d$, but unlike on HSTs it is not bounded by $2^k-1$.
  We obtain our results by a dual fitting analysis where the dual solution is
constructed step-by-step backwards in time. Unlike the forward-time approach
typical of online primal-dual analyses, this allows us to combine information
from the past and the future when assigning dual variables. We believe this
method can be useful also for other problems. Using this technique, we also
provide a dual fitting proof of the $k$-competitiveness of Double Coverage for
the $k$-server problem on trees.
