Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation

Authors Yu Chen, Sampath Kannan, Sanjeev Khanna



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.30.pdf
  • Filesize: 0.52 MB
  • 19 pages

Document Identifiers

Author Details

Yu Chen
  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA
Sampath Kannan
  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA
Sanjeev Khanna
  • Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA, USA

Acknowledgements

We thank the anonymous reviewers for their valuable feedback. This work was supported in part by NSF awards CCF-1617851, CCF-1733794, CCF-1763307, CCF-1763514, and CCF-1934876.

Cite AsGet BibTex

Yu Chen, Sampath Kannan, and Sanjeev Khanna. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.30

Abstract

We consider the problem of designing sublinear time algorithms for estimating the cost of minimum metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any ε > 0, there exists an Õ(n/ε^O(1)) time algorithm that returns a (1 + ε)-approximate estimate of the MST cost. This result immediately implies an Õ(n/ε^O(1)) time algorithm to estimate the TSP cost to within a (2 + ε) factor for any ε > 0. However, no o(n²) time algorithms are known to approximate metric TSP to a factor that is strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + ε)-approximate estimation algorithms for metric TSP with Õ(n) time for any fixed ε > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. On the algorithmic side, we first consider the graphic TSP problem where the metric D corresponds to shortest path distances in a connected unweighted undirected graph. We show that there exists an Õ(n) time algorithm that estimates the cost of graphic TSP to within a factor of (2-ε₀) for some ε₀ > 0. This is the first sublinear cost estimation algorithm for graphic TSP that achieves an approximation factor less than 2. We also consider another well-studied special case of metric TSP, namely, (1,2)-TSP where all distances are either 1 or 2, and give an Õ(n^1.5) time algorithm to estimate optimal cost to within a factor of 1.625. Our estimation algorithms for graphic TSP as well as for (1,2)-TSP naturally lend themselves to Õ(n) space streaming algorithms that give an 11/6-approximation for graphic TSP and a 1.625-approximation for (1,2)-TSP. These results motivate the natural question if analogously to metric MST, for any ε > 0, (1 + ε)-approximate estimates can be obtained for graphic TSP and (1,2)-TSP using Õ(n) queries. We answer this question in the negative - there exists an ε₀ > 0, such that any algorithm that estimates the cost of graphic TSP ((1,2)-TSP) to within a (1 + ε₀)-factor, necessarily requires Ω(n²) queries. This lower bound result highlights a sharp separation between the metric MST and metric TSP problems. Similarly to many classical approximation algorithms for TSP, our sublinear time estimation algorithms utilize subroutines for estimating the size of a maximum matching in the underlying graph. We show that this is not merely an artifact of our approach, and that for any ε > 0, any algorithm that estimates the cost of graphic TSP or (1,2)-TSP to within a (1 + ε)-factor, can also be used to estimate the size of a maximum matching in a bipartite graph to within an ε n additive error. This connection allows us to translate known lower bounds for matching size estimation in various models to similar lower bounds for metric TSP cost estimation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • sublinear algorithms
  • TSP
  • streaming algorithms
  • query complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. URL: https://sublinear.info/71.
  2. Anna Adamaszek, Matthias Mnich, and Katarzyna Paluch. New approximation algorithms for (1, 2)-tsp. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  3. Hyung-Chan An, Robert D. Kleinberg, and David B. Shmoys. Improving christofides' algorithm for the s-t path TSP. J. ACM, 62(5):34:1-34:28, 2015. Google Scholar
  4. Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1723-1742. SIAM, 2017. Google Scholar
  5. Piotr Berman and Marek Karpinski. 8/7-approximation algorithm for (1, 2)-tsp. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 641-648. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  6. Andrej Bogdanov, Kenji Obata, and Luca Trevisan. A lower bound for testing 3-colorability in bounded-degree graphs. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 93-102. IEEE, 2002. Google Scholar
  7. Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput., 34(6):1370-1379, 2005. Google Scholar
  8. Chandra Chekuri and Kent Quanrud. Approximating the held-karp bound for metric TSP in nearly-linear time. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 789-800, 2017. Google Scholar
  9. Chandra Chekuri and Kent Quanrud. Fast approximations for metric-TSP via linear programming. CoRR, abs/1802.01242, 2018. URL: http://arxiv.org/abs/1802.01242.
  10. Artur Czumaj and Christian Sohler. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing, 39(3):904-922, 2009. Google Scholar
  11. Zhihan Gao. On the metric s-t path traveling salesman problem. SIAM Review, 60(2):409-426, 2018. Google Scholar
  12. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. Google Scholar
  13. Michael Kapralov, Slobodan Mitrović, Ashkan Norouzi-Fard, and Jakab Tardos. Space efficient approximation to maximum matching size from uniform edge samples. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1753-1772. SIAM, 2020. Google Scholar
  14. Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability bounds for TSP. J. Comput. Syst. Sci., 81(8):1665-1677, 2015. Google Scholar
  15. Matthias Mnich and Tobias Mömke. Improved integrality gap upper bounds for traveling salesperson problems with distances one and two. European Journal of Operational Research, 266(2):436-457, 2018. Google Scholar
  16. Tobias Mömke and Ola Svensson. Approximating graphic TSP by matchings. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 560-569, 2011. URL: https://doi.org/10.1109/FOCS.2011.56.
  17. Tobias Mömke and Ola Svensson. Removing and adding edges for the traveling salesman problem. Journal of the ACM (JACM), 63(1):2, 2016. Google Scholar
  18. Marcin Mucha. 13/9-approximation for graphic tsp. Theory of computing systems, 55(4):640-657, 2014. Google Scholar
  19. Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 327-336, 2008. Google Scholar
  20. Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1123-1131. Society for Industrial and Applied Mathematics, 2012. Google Scholar
  21. Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. Personal communication, 2019. Google Scholar
  22. Christos H Papadimitriou and Mihalis Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1-11, 1993. Google Scholar
  23. Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theor. Comput. Sci., 381(1-3):183-196, 2007. Google Scholar
  24. András Sebö and Anke van Zuylen. The salesman’s improved paths: A 3/2+1/34 approximation. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 118-127, 2016. Google Scholar
  25. András Sebö and Jens Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-tsp, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597-629, 2014. Google Scholar
  26. Vera Traub and Jens Vygen. Beating the integrality ratio for s-t-tours in graphs. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 766-777, 2018. Google Scholar
  27. Vera Traub and Jens Vygen. Approaching 3/2 for the s-t-path TSP. J. ACM, 66(2):14:1-14:17, 2019. URL: https://doi.org/10.1145/3309715.
  28. Jens Vygen. New approximation algorithms for the tsp, 2012. Google Scholar
  29. Douglas B. West. Introduction to graph theory. Prentice-Hall Inc., 1996. Google Scholar
  30. Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM Journal on Computing, 41(4):1074-1093, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail