Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
Abstract
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.
Fields of Study & Subjects
Vehicle Routing Optimization Methods
Constraint Satisfaction and Optimization
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 5374–5439
- Publication date
- 1 January 2026
- Language
- EN