A Constant-Factor Approximation for Directed Latency

In the DIRECTED LATENCY problem, we are given an asymmetric metric space (V ∪ s, c) on a set V of clients and a depot s. We are looking for a path P starting in s that visits all clients and minimizes the sum of the clients' waiting times (also known as latency) before being visited on the path. This models problems in logistics where client satisfaction is essential, as opposed to objectives like in TSP, where the goal is to make the salesperson as happy as possible.

In contrast to the symmetric version of this problem (also known as the DELIVERYPERSON problem and the TRAVELING REPAIRPERSON problem in the literature), there are significant gaps in our understanding of DIRECTED LATENCY. The best approximation factor has remained at O(log |V|), as shown by [Friggstad, Salavatipour, and Svitkina, '13], for more than a decade. Only recently, [Friggstad and Swamy, '22] presented a constant-factor approximation, but in quasi-polynomial time. Both results follow similar ideas: they consider buckets with geometrically increasing distances, build a path on each bucket, and then stitch together all these paths to get a feasible solution. Building a path on each bucket can be done cheaply thanks to developments in ASYMMETRIC PATH TSP. However, stitching these paths together incurs a logarithmic factor increase in the latency. [Friggstad and Swamy, '22] showed that by guessing a vertex from each bucket and augmenting a standard LP relaxation with these guesses, one can reduce the stitching cost. Unfortunately, the number of buckets is logarithmic in the number of vertices, so the running time of their algorithm is quasi-polynomial.

In this paper, we present the first constant-factor approximation for DIRECTED LATENCY in polynomial time by introducing a completely new way of bucketing, which helps us strengthen a standard LP relaxation with less aggressive guessing. Although the resulting LP is no longer a relaxation of DIRECTED LATENCY, it still admits a good solution. Then, we present a rounding algorithm for fractional solutions of our LP, which at a high level follows the rounding algorithm by [Friggstad and Swamy, '22] but with many new ingredients, crucially exploiting the way we restricted the feasibility region of the LP formulation.