  We give the first constant-factor approximation for the Directed Latency
problem in quasi-polynomial time. Here, the goal is to visit all nodes in an
asymmetric metric with a single vehicle starting at a depot $r$ to minimize the
average time a node waits to be visited by the vehicle. The approximation
guarantee is an improvement over the polynomial-time $O(\log n)$-approximation
[Friggstad, Salavatipour, Svitkina, 2013] and no better quasi-polynomial time
approximation algorithm was known.
  To obtain this, we must extend a recent result showing the integrality gap of
the Asymmetric TSP-Path LP relaxation is bounded by a constant [K\"{o}hne,
Traub, and Vygen, 2019], which itself builds on the breakthrough result that
the integrality gap for standard Asymmetric TSP is also a constant [Svensson,
Tarnawsi, and Vegh, 2018]. We show the standard Asymmetric TSP-Path integrality
gap is bounded by a constant even if the cut requirements of the LP relaxation
are relaxed from $x(\delta^{in}(S)) \geq 1$ to $x(\delta^{in}(S)) \geq \rho$
for some constant $1/2 < \rho \leq 1$. We also give a better approximation
guarantee in the special case of Directed Latency in regret metrics where the
goal is to find a path $P$ minimize the average time a node $v$ waits in excess
of $c_{rv}$, i.e. $\frac{1}{|V|} \cdot \sum_{v \in V} (c_v(P)-c_{rv})$.
