A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917662675697664 |
|---|---|
| author | Armbruster, Susanne Mnich, Matthias Nägele, Martin |
| author_facet | Armbruster, Susanne Mnich, Matthias Nägele, Martin |
| contents | We present a new $(\frac32+\frac1{\mathrm{e}})$-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately $1.868$ holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of $\frac52$ for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_06244 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP Armbruster, Susanne Mnich, Matthias Nägele, Martin Data Structures and Algorithms We present a new $(\frac32+\frac1{\mathrm{e}})$-approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metric Traveling Salesperson Problem (TSP) where a specified subset of vertices needs to appear on the output Hamiltonian cycle in a given order, and the task is to compute a cheapest such cycle. Our approximation guarantee of approximately $1.868$ holds with respect to the value of a natural new linear programming (LP) relaxation for Ordered TSP. Our result significantly improves upon the previously best known guarantee of $\frac52$ for this problem and thereby considerably reduces the gap between approximability of Ordered TSP and metric TSP. Our algorithm is based on a decomposition of the LP solution into weighted trees that serve as building blocks in our tour construction. |
| title | A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.06244 |