A Constant-Factor Approximation for Directed LatencyOberseminar Discrete Optimization

by Dr Jannis Blauth (ETH Zürich)

Thursday Jul 23, 2026, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

In the Directed Latency problem, we are given an asymmetric metric space 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. 

In contrast to the symmetric version of this problem, 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. 

[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.

This is joint work with Ramin Mousavi (STOC '26).

 

The Oberseminar takes place in the Seminarraum, 1st floor. Participants are invited to have coffee or tea in the lounge before.