A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk)

Autor:	Karlin, Anna R.
Jazyk:	angličtina
Rok vydání:	2023
Předmět:	Traveling Salesperson Problem approximation algorithm Theory of computation → Approximation algorithms analysis
DOI:	10.4230/lipics.icalp.2023.1
Popis:	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]. LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 1:1-1:1
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::535fd510a7037826c17b4fd302bf79a3 Zobrazit plný text záznamu