The Steiner Traveling Salesman Problem with online edge blockages
The Steiner Traveling Salesman Problem with as many as k online edge blockages is considered. First a lower bound on the competitive ratio is shown; then an exponential-time online optimal algorithm for the problem is presented; and lastly a polynomial-time online asymptotically optimal algorithm is presented. Experimental results show that the polynomial-time online algorithm takes only a fraction of the running time of the offline optimal algorithm, yet produces solutions of competitive quality to the offline optimal solutions.
traveling salesman problem online edge blockage competitive ratio online algorithm steiner tsp