Theory Seminar: Dr. Jannis Blauth, "A Constant-Factor Approximation for Directed Latency."

Abstract: In the Directed Latency problem, we are given an asymmetric metric on a set of vertices (or clients), and a given depot s. We seek a path P starting at s and visiting all the clients so as to minimize the sum of client waiting times (also known as latency) before being visited on the path.

In contrast to the symmetric version of this problem (also known as the Deliveryperson problem and the Repairperson problem in the literature), there are significant gaps in our understanding of Directed Latency.

The best approximation factor has remained at O(log n), where n is the number of clients, for more than a decade [Friggstad, Salavatipour, and Svitkina, '13]. 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 paths in each bucket, and then stitch together all these paths to get a feasible solution. [Friggstad and Swamy, '22] showed if we guess a vertex from each bucket and augment a standard LP relaxation with these guesses, then one can reduce the stitching cost. 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. We present a rounding algorithm for fractional solutions of our LP, crucially exploiting the way we restricted the feasibility region of the LP formulation.

Short bio: In February 2025, Jannis Blauth joined the group of Rico Zenklusen as a Postdoctoral Researcher at the Institute for Operations Research at ETH Zurich. In 2024, he completed his PhD at the University of Bonn under the supervision of Jens Vygen.

His main research interests lie in combinatorial optimization, with a particular focus on the design of approximation algorithms. In addition, he is interested in modeling real-world problems and developing efficient heuristics to address them.

These interests are reflected in his PhD thesis entitled, "Vehicle Routing in Theory and Practice."