The online traveling salesman problem against fair adversaries

The online traveling salesman problem against fair adversaries

0.00 Avg rating0 Votes
Article ID: iaor20022014
Country: United States
Volume: 13
Issue: 2
Start Page Number: 138
End Page Number: 148
Publication Date: Mar 2001
Journal: INFORMS Journal On Computing
Authors: , , ,
Keywords: computational analysis, vehicle routing & scheduling, networks
Abstract:

In the online traveling saleman problem, requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The saleman 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 saleman that finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have led us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is 3/2-competitive against the conventional 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 exists an algorithm with a specific competitive ratio and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.

Reviews

Required fields are marked *. Your email address will not be published.