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.