License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.1
URN: urn:nbn:de:0030-drops-180531
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18053/
Karlin, Anna R.
A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk)
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].
BibTeX - Entry
@InProceedings{karlin:LIPIcs.ICALP.2023.1,
author = {Karlin, Anna R.},
title = {{A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18053},
URN = {urn:nbn:de:0030-drops-180531},
doi = {10.4230/LIPIcs.ICALP.2023.1},
annote = {Keywords: Traveling Salesperson Problem, approximation algorithm}
}
|
Keywords: |
|
Traveling Salesperson Problem, approximation algorithm |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
