{"ID":2852811,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.17595","arxiv_id":"2510.17595","title":"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. 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.","short_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...","url_abs":"https://arxiv.org/abs/2510.17595","url_pdf":"https://arxiv.org/pdf/2510.17595v1","authors":"[\"Manuel Christalla\",\"Luise Puhlmann\",\"Vera Traub\"]","published":"2025-10-20T14:47:02Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}