The Traveling Salesman Problem (TSP) is a well-known combinatorial #R##N#optimization problem. We are concerned here with online versions of a #R##N#generalization of the TSP on metric spaces where the server doesn't have #R##N#to accept all requests. Associated with each request (to visit a point in the #R##N#metric space) is a penalty (incurred if the request is rejected). Requests #R##N#are revealed over time to a server, initially at a given origin, who must #R##N#decide which requests to serve in order to minimize the time to serve all #R##N#accepted requests plus the sum of the penalties associated with the #R##N#rejected requests. #R##N##R##N#In a first online version of this problem (basic version), we assume that the #R##N#server's decision to accept or reject a request can be made any time after #R##N#its release date. In a second online version of this problem (real-time #R##N#version), we assume that the server's decision to accept or reject a #R##N#request must be made exactly at its release date.#R##N##R##N#After reviewing prior results on the online TSP, we first provide an optimal #R##N#2-competitive online algorithm for the basic version of the problem in a #R##N#general metric space, improving prior results from the literature.  We then#R##N#consider the real-time version of the problem and show that there can't be #R##N#any finite $c$-competitive online algorithm in a general metric space.
['Patrick Jaillet', 'Xin Lu']
Online Traveling Salesman Problems with Flexibility