2019/12/12 by Zachary Friggstad, Friggstad, Zachary, Chaitanya Swamy +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems
paper · doi:10.48550/arxiv.1912.06198
openalex publication_date 2019/12/12 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We give the first constant-factor approximation for the Directed Latency problem in quasi-polynomial time. Here, the goal is to visit all nodes in an asymmetric metric with a single vehicle starting at a depot r to minimize the average time a node waits to be visited by the vehicle. The approximation guarantee is an improvement over the polynomial-time O(log n)-approximation [Friggstad, Salavatipour, Svitkina, 2013] and no better quasi-polynomial time approximation algorithm was known. To obtain this, we must extend a recent result showing the integrality gap of the Asymmetric TSP-Path LP relaxation is bounded by a constant [Köhne, Traub, and Vygen, 2019], which itself builds on the breakthrough result that the integrality gap for standard Asymmetric TSP is also a constant [Svensson, Tarnawsi, and Vegh, 2018]. We show the standard Asymmetric TSP-Path integrality gap is bounded by a constant even if the cut requirements of the LP relaxation are relaxed from x(δin(S)) ≥ 1 to x(δin(S)) ≥ ρ for some constant 1/2 < ρ≤ 1. We also give a better approximation guarantee in the special case of Directed Latency in regret metrics where the goal is to find a path P minimize the average time a node v waits in excess of crv, i.e. (1)/(|V|) ⋅ ∑v ∈ V (cv(P)-crv).