The Online Prize-Collecting Traveling Salesman Problem
5,00 €
3,00 €
     
SINTESI
We study the online version of the Prize-Collecting Traveling Salesman Problem (PCTSP), a generalization of the Traveling Salesman Problem (TSP). In the TSP, the salesman has to visit a set of citieswhile minimizing the length of the overall tour. In the PCTSP, each city has a given weight and penalty, and the goal is to collect a given quota of the weights of the cities while minimizing the length of thetour plus the penalties of the cities not in the tour. In the online version, cities arrive over time. We give a 7/3-competitive algorithm for the problem, which compares with a lower bound of 2 on the competitive ratio of any deterministic algorithm. We also consider the special case of cities located on the real halfline, for which we prove lower and upper bounds of 1.89 and 2, respectively, on the competitive ratio ofdeterministic algorithms.
pagine: 20
formato: 17 x 24
ISBN: 978-88-548-0976-5
data pubblicazione: Febbraio 2007
editore: Aracne
collana: Dipartimento di Informatica e Sistemistica “Antonio Ruberti” della “Sapienza” Università di Roma | 2006/8
SINTESI
Informativa      Aracneeditrice.it si avvale di cookie, anche di terze parti, per offrirti il migliore servizio possibile. Cliccando 'Accetto' o continuando la navigazione ne acconsenti l'utilizzo. Per saperne di più
Accetto