BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:A Constant-Factor Approximation for Directed Latency [Oberseminar 
 Discrete Optimization]
DTSTART:20260723T161500Z
DTEND:20260723T171500Z
DTSTAMP:20260913T020200Z
UID:indico-event-1457@math-events.uni-bonn.de
DESCRIPTION:Speakers: Jannis Blauth (ETH Zürich)\n\nIn the Directed Laten
 cy 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. \nIn contrast to the symme
 tric version of this problem\, there are significant gaps in our understan
 ding 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] p
 resented a constant-factor approximation\, but in quasi-polynomial time. 
 \nBoth results follow similar ideas: they consider buckets with geometrica
 lly increasing distances\, build a path on each bucket\, and then stitch 
 together all these paths to get a feasible solution. \n[Friggstad and Swa
 my\, ’22] showed that by guessing a vertex from each bucket and augmenti
 ng a standard LP relaxation with these guesses\, one can reduce the stitc
 hing cost. Unfortunately\, the number of buckets is logarithmic in the nu
 mber of vertices\, so the running time of their algorithm is quasi-polynom
 ial.\nIn this paper\, we present the first constant-factor approximation f
 or Directed Latency in polynomial time by introducing a completely new way
  of bucketing\, which helps us strengthen a standard LP relaxation with le
 ss aggressive guessing.This is joint work with Ramin Mousavi (STOC '26).\n
  \nThe Oberseminar takes place in the Seminarraum\, 1st floor. Participan
 ts are invited to have coffee or tea in the lounge before.\n \n \n\nhttp
 s://math-events.uni-bonn.de/event/1457/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/1457/
END:VEVENT
END:VCALENDAR