Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 7 of 0
Back to Result List

The Online-TSP Against Fair Adversaries

Please always quote using this URN: urn:nbn:de:0297-zib-5779
  • In the online traveling salesman problem requests for visits to cities (points 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 which 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 lead 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 ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio $\frac{1+\sqrt{17}}{4}\approx 1.28$ 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Michiel Blom, Sven Krumke, Willem de Paepe, Leen Stougie
Document Type:ZIB-Report
Tag:Competitive Analysis; Online-Algorithms; Vehicle Routing
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
CCS-Classification:F. Theory of Computation / F.1 COMPUTATION BY ABSTRACT DEVICES / F.1.2 Modes of Computation
Date of first Publication:2000/03/23
Series (Serial Number):ZIB-Report (00-09)
ZIB-Reportnumber:00-09
Published in:Appeared in: Informs Journal on Computing 13 (2001) pp. 138-148. A prel. vers. appeared in: Proc. of the 4th Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science, vol. 1767, Springer 2000, 137-149
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.