The online TSP against fair adversaries

In the online traveling salesman problem, requests for visits to cities (po ints in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman tha t finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comp aring the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline s olution. Objections against such omnipotent adversaries have lead us to dev ise an adversary that is in a natural way, in the context of routing proble ms, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by R-0(+), the non-negative part of the real line. We s how that a very natural strategy is 3/2-competitive against the conventiona l adversary, which matches the lower-bound on competitive ratios achievable for algorithms for this problem. Against the more "fair adversary", that we propose, we show that there exis ts an algorithm with competitive ratio (1+root 17)/4 approximate to 1.28 an d provide a matching lower bound. We also show competitiveness results for a special class of algorithms (cal led zealous algorithms) that do not allow waiting time for the server as lo ng as there are requests unserved.