2026-07-20T05:29:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2172 2024-03-06T11:08:50Z ddc:004 open_access

Online Traveling Salesman Problems with Flexibility Jaillet, Patrick Lu, Xin Online TSP service flexibility rejection options The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem. We are concerned here with online versions of a generalization of the TSP on metric spaces where the server doesn't have to accept all requests. Associated with each request (to visit a point in the metric space) is a penalty (incurred if the request is rejected). Requests are revealed over time to a server, initially at a given origin, who must decide which requests to serve in order to minimize the time to serve all accepted requests plus the sum of the penalties associated with the rejected requests. In a first online version of this problem (basic version), we assume that the server's decision to accept or reject a request can be made any time after its release date. In a second online version of this problem (real-time version), we assume that the server's decision to accept or reject a request must be made exactly at its release date. After reviewing prior results on the online TSP, we first provide an optimal 2-competitive online algorithm for the basic version of the problem in a general metric space, improving prior results from the literature. We then consider the real-time version of the problem and show that there can't be any finite $c$-competitive online algorithm in a general metric space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patrick Jaillet and Xin Lu 2009 Is Part Of Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09261.19 urn:nbn:de:0030-drops-21720 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.19 eng https://creativecommons.org/licenses/by/4.0/legalcode