LIPIcs.ICALP.2023.1.pdf
- Filesize: 331 kB
- 1 pages
Document
A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk)
Author
-
Part of:
Volume:
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-07-05
Cite As Get BibTex
Anna R. Karlin. A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICALP.2023.1
Abstract
We describe recent joint work with Nathan Klein and Shayan Oveis Gharan showing that for any metric TSP instance, the max entropy algorithm studied by [Anna R. Karlin et al., 2021] returns a solution of expected cost at most 3/2-ε times the cost of the optimal solution to the subtour elimination LP and hence is a 3/2-ε approximation for the metric TSP problem. The research discussed comes from [Anna R. Karlin et al., 2021], [Anna R. Karlin et al., 2022] and [Anna R. Karlin et al., 2022].
Subject Classification
ACM Subject Classification
- Theory of computation → Approximation algorithms analysis
Keywords
- Traveling Salesperson Problem
- approximation algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric TSP. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 32-45. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451009.
- Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved bound on the integrality gap of the subtour LP for TSP. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 832-843. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00084.
- Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved deterministic approximation algorithm for metric TSP. CoRR, abs/2212.06296, 2022. URL: https://doi.org/10.48550/arXiv.2212.06296.