Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
Manuel Christalla, Luise Puhlmann, Vera Traub
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…
cs.DS2023
Improved guarantees for the a priori TSP
Jannis Blauth, Meike Neuwohner, Luise Puhlmann +1
We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space $…