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 $…