Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2510.17595 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918164201209856 |
|---|---|
| author | Christalla, Manuel Puhlmann, Luise Traub, Vera |
| author_facet | Christalla, Manuel Puhlmann, Luise Traub, Vera |
| contents | In Asymmetric A Priori TSP (with independent activation probabilities) we are given an instance of the Asymmetric Traveling Salesman Problem together with an activation probability for each vertex. The task is to compute a tour that minimizes the expected length after short-cutting to the randomly sampled set of active vertices.
We prove a polynomial lower bound on the adaptivity gap for Asymmetric A Priori TSP. Moreover, we show that a poly-logarithmic approximation ratio, and hence an approximation ratio below the adaptivity gap, can be achieved by a randomized algorithm with quasi-polynomial running time.
To achieve this, we provide a series of polynomial-time reductions. First we reduce to a novel generalization of the Asymmetric Traveling Salesman Problem, called Hop-ATSP. Next, we use directed low-diameter decompositions to obtain structured instances, for which we then provide a reduction to a covering problem. Eventually, we obtain a polynomial-time reduction of Asymmetric A Priori TSP to a problem of finding a path in an acyclic digraph minimizing a particular objective function, for which we give an O(log n)-approximation algorithm in quasi-polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17595 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap Christalla, Manuel Puhlmann, Luise Traub, Vera Data Structures and Algorithms In Asymmetric A Priori TSP (with independent activation probabilities) we are given an instance of the Asymmetric Traveling Salesman Problem together with an activation probability for each vertex. The task is to compute a tour that minimizes the expected length after short-cutting to the randomly sampled set of active vertices. We prove a polynomial lower bound on the adaptivity gap for Asymmetric A Priori TSP. Moreover, we show that a poly-logarithmic approximation ratio, and hence an approximation ratio below the adaptivity gap, can be achieved by a randomized algorithm with quasi-polynomial running time. To achieve this, we provide a series of polynomial-time reductions. First we reduce to a novel generalization of the Asymmetric Traveling Salesman Problem, called Hop-ATSP. Next, we use directed low-diameter decompositions to obtain structured instances, for which we then provide a reduction to a covering problem. Eventually, we obtain a polynomial-time reduction of Asymmetric A Priori TSP to a problem of finding a path in an acyclic digraph minimizing a particular objective function, for which we give an O(log n)-approximation algorithm in quasi-polynomial time. |
| title | Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.17595 |