Back to Search
Start Over
A constant-factor approximation for directed latency in quasi-polynomial time.
- Source :
-
Journal of Computer & System Sciences . Jun2022, Vol. 126, p44-58. 15p. - Publication Year :
- 2022
-
Abstract
- 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 along P. We give the first constant-factor approximation guarantee for DirLat , but in quasi-polynomial time. A key ingredient of our result, and our chief technical contribution, is an extension of a recent result of Köhne et al. (2019) [17] showing that the integrality gap of the natural Held-Karp relaxation for asymmetric TSP-Path (ATSPP) is at most a constant. 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *TIME
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 126
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 155363930
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.12.001