New Approximation-based Local Search Algorithms for the Probabilistic Traveling Salesman Problem

In this paper we present new local search algorithms for the Probabilistic Trav-eling Salesman Problem (PTSP) using sampling and ad-hoc approximation. These algorithms improve both runtime and solution quality of state-of-the-art local search algorithms for the PTSP.