{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T18:10:35Z","timestamp":1791396635217,"version":"4.3.3"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We study integrality gaps and approximability of three closely related problems on directed graphs with edge lengths that satisfy the triangle inequality. Given two specified vertices $s$ and $t$, two of these problems ask to find an $s$-$t$ path in the graph visiting all other vertices. In the asymmetric traveling salesman path problem (ATSPP), the objective is to minimize the total length of this path. In the directed latency problem, the objective is to minimize the sum of the latencies of the vertices, where the latency of a vertex $v$ is the distance from $s$ to $v$ along the path. The third problem that we study is the $k$-person ATSPP, in which the goal is to find $k$ paths from $s$ to $t$, of minimum total length, such that every vertex is on at least one of these paths. All of these problems are NP-hard. The best known approximation algorithms for ATSPP had ratio $O(\\log n)$ [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197--209], [U. Feige and M. Singh, \u201cImproved approximation ratios for traveling salesperson tours and paths in directed graphs,\u201d in Proceedings of the 10th APPROX, 2007, pp. 107--118] until the recent result that improves it to $O(\\log n\/\\log \\log n)$ [A. Asadpour et al., \u201cAn $O(\\log n\/\\log \\log n)$-approximation algorithm for the asymmetric traveling salesman problem,\u201d in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 379--389], [U. Feige and M. Singh, \u201cImproved approximation ratios for traveling salesperson tours and paths in directed graphs,\u201d in Proceedings of the 10th APPROX, 2007, pp. 107--118]. However, the best known bound on the integrality gap of any linear programming relaxation for ATSPP is only $O(\\sqrt{n})$. For directed latency, the best previously known approximation algorithm has a guarantee of $O(n^{1\/2+\\epsilon})$ for any constant $\\epsilon&gt;0$ [V. Nagarajan and R. Ravi, \u201cThe directed minimum latency problem,\u201d in Proceedings of the 11th APPROX, 2008, pp. 193--206]. We present a new algorithm for the ATSPP problem that has an approximation ratio of $O(\\log n)$, but whose analysis also upper bounds the integrality gap of the standard LP relaxation of ATSPP by the same factor. This solves an open problem posed in [C. Chekuri and M. Pal, Theory Comput., 3 (2007), pp. 197--209]. We then pursue a deeper study of this linear program and its variations, which leads to an $O(\\log n)$-approximation for the directed latency problem, a significant improvement over previously known results. Our result for $k$-person ATSPP is an $O(k^2 \\log n)$-approximation that bounds the integrality gap of a linear programming relaxation by the same factor. We are not aware of any previous work on this problem.<\/jats:p>","DOI":"10.1137\/100797357","type":"journal-article","created":{"date-parts":[[2013,7,30]],"date-time":"2013-07-30T11:16:53Z","timestamp":1375183013000},"page":"1596-1619","source":"Crossref","is-referenced-by-count":8,"title":["Asymmetric Traveling Salesman Path and Directed Latency Problems"],"prefix":"10.1137","volume":"42","author":[{"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zoya","family":"Svitkina","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,7,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1986200100791"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"H.C. An, R. Kleinberg, and D. B. Shmoys,\n                      Improving Christofides' algorithm for the s-t path TSP\n                      , in Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 875-886.","DOI":"10.1145\/2213977.2214055"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/07068151X"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Asadpour, M. X. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi,\n                      An $O(\\log n\/\\log \\log n)$-approximation algorithm for the asymmetric traveling salesman problem\n                      , in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 379-389.","DOI":"10.1137\/1.9781611973075.32"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, D. Coppersmith, B. Pulleyblank, P. Raghavan, and M. Sudan,\n                      The minimum latency problem\n                      , in Proceedings of the 26th ACM Symposium on Theory of Computing, 1994, pp. 163-171.","DOI":"10.1145\/195058.195125"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"D. Chakrabarty and C. Swamy,\n                      Facility location with client latencies: Linear programming based techniques for minimum latency problems\n                      , in Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization, 2011, pp. 92-103.","DOI":"10.1007\/978-3-642-20807-2_8"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"M. Charikar, M. X. Goemans, and H. Karloff,\n                      On the integrality ratio for asymmetric TSP\n                      , in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004, pp. 101-107.","DOI":"10.1109\/FOCS.2004.45"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar,\n                      Paths, trees, and minimum latency tours\n                      , in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, 2003, pp. 36-45.","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a010"},{"key":"atypb10","unstructured":"N. Christofides,\n                      Worst-Case Analysis of a New Heuristic for the Traveling Salesman Problem\n                      , Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"U. Feige and M. Singh,\n                      Improved approximation ratios for traveling salesperson tours and paths in directed graphs\n                      , in Proceedings of the 10th APPROX, 2007, pp. 104-118.","DOI":"10.1007\/978-3-540-74208-1_8"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70459-X"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90102-6"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120103"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"Z. Friggstad, A. Gupta, and M. Singh,\n                      An improved integrality gap for asymmetric TSP paths\n                      , in Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, 2013, pp. 181-192.","DOI":"10.1007\/978-3-642-36694-9_16"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585867"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , 2nd ed., Ann. Discrete Math. 57, North-Holland, Amsterdam, The Netherlands, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"atypb18","unstructured":"G. Gutin and A. P. Punnen, eds.\n                      Traveling Salesman Problem and Its Variations\n                      , Springer, Berlin, 2002."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90016-I"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120314"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082041"},{"key":"atypb22","unstructured":"J. Kleinberg and D. P. Williamson,\n                      Unpublished note\n                      , 1998."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0046-8"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"E. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. Shmoys, eds.\n                      The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization\n                      , John Wiley & Sons, New York, 1985.","DOI":"10.2307\/2582681"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.05.009"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02097807"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"V. Nagarajan and R. Ravi,\n                      Poly-logarithmic approximation algorithms for directed vehicle routing problems\n                      , in Proceedings of the 10th APPROX, 2007, pp. 257-270.","DOI":"10.1007\/978-3-540-74208-1_19"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"V. Nagarajan and R. Ravi,\n                      The directed minimum latency problem\n                      , in Proceedings of the 11th APPROX, 2008, pp. 193-206.","DOI":"10.1007\/978-3-540-85363-3_16"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0008-z"},{"key":"atypb30","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency\n                      , Springer, Berlin, 2003."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90028-V"},{"key":"atypb32","unstructured":"D. P. Williamson,\n                      Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem\n                      , M.S. Thesis, MIT, Cambridge, MA, 1990."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120913"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100797357","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:12:25Z","timestamp":1787339545000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100797357"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/100797357"],"URL":"https:\/\/doi.org\/10.1137\/100797357","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}