A constant-factor approximation for directed latency in quasi-polynomial time.

We consider the directed minimum latency problem (DirLat), wherein we seek a path P visiting all points (or clients) in a given asymmetric metric starting at a given root node r , so as to minimize the sum of the client waiting times along P. We give the first constant-factor approximation guarantee for DirLat , but in quasi-polynomial time. A key ingredient of our result, and our chief technical contribution, is an extension of a recent result of Köhne et al. (2019) [17] showing that the integrality gap of the natural Held-Karp relaxation for asymmetric TSP-Path (ATSPP) is at most a constant. We also give a better approximation guarantee for the minimum total-regret problem , where the goal is to find a path P that minimizes the total time that nodes spend in excess of their shortest-path distances from r , which can be cast as a special case of DirLat involving so-called regret metrics. [ABSTRACT FROM AUTHOR]