2026-07-22T06:49:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12918 2024-03-06T10:51:05Z ddc:004 open_access

A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time Friggstad, Zachary Swamy, Chaitanya Approximation Algorithms Directed Latency TSP We consider the directed minimum latency problem (DirLat), wherein we seek a path P visiting all points (or clients) in a given asymmetric metric starting at a given root node r, so as to minimize the sum of the client waiting times, where the waiting time of a client v is the length of the r-v portion of P. We give the first constant-factor approximation guarantee for DirLat, but in quasi-polynomial time. Previously, a polynomial-time O(log n)-approximation was known [Z. Friggstad et al., 2013], and no better approximation guarantees were known even in quasi-polynomial time. A key ingredient of our result, and our chief technical contribution, is an extension of a recent result of [A. Köhne et al., 2019] showing that the integrality gap of the natural Held-Karp relaxation for asymmetric TSP-Path (ATSPP) is at most a constant, which itself builds on the breakthrough similar result established for asymmetric TSP (ATSP) by Svensson et al. [O. Svensson et al., 2018]. We show that the integrality gap of the Held-Karp relaxation for ATSPP 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 for the minimum total-regret problem, where the goal is to find a path P that minimizes the total time that nodes spend in excess of their shortest-path distances from r, which can be cast as a special case of DirLat involving so-called regret metrics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zachary Friggstad and Chaitanya Swamy 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.52 urn:nbn:de:0030-drops-129183 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.52 eng https://creativecommons.org/licenses/by/3.0/legalcode