  We consider the online $k$-taxi problem, a generalization of the $k$-server
problem, in which $k$ taxis serve a sequence of requests in a metric space. A
request consists of two points $s$ and $t$, representing a passenger that wants
to be carried by a taxi from $s$ to $t$. The goal is to serve all requests
while minimizing the total distance traveled by all taxis. The problem comes in
two flavors, called the easy and the hard $k$-taxi problem: In the easy
$k$-taxi problem, the cost is defined as the total distance traveled by the
taxis; in the hard $k$-taxi problem, the cost is only the distance of empty
runs.
  The hard $k$-taxi problem is substantially more difficult than the easy
version with at least an exponential deterministic competitive ratio,
$\Omega(2^k)$, admitting a reduction from the layered graph traversal problem.
In contrast, the easy $k$-taxi problem has exactly the same competitive ratio
as the $k$-server problem. We focus mainly on the hard version. For
hierarchically separated trees (HSTs), we present a memoryless randomized
algorithm with competitive ratio $2^k-1$ against adaptive online adversaries
and provide two matching lower bounds: for arbitrary algorithms against
adaptive adversaries and for memoryless algorithms against oblivious
adversaries. Due to well-known HST embedding techniques, the algorithm implies
a randomized $O(2^k\log n)$-competitive algorithm for arbitrary $n$-point
metrics. This is the first competitive algorithm for the hard $k$-taxi problem
for general finite metric spaces and general $k$. For the special case of
$k=2$, we obtain a precise answer of $9$ for the competitive ratio in general
metrics. With an algorithm based on growing, shrinking and shifting regions, we
show that one can achieve a constant competitive ratio also for the hard
$3$-taxi problem on the line (abstracting the scheduling of three elevators).
