2025/10/20 by Manuel Christalla, Christalla, Manuel, Luise Puhlmann +3
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2510.17595
openalex publication_date 2025/10/20 · openalex created_date 2025/10/22 · openalex updated_date 2026/07/28
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.