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 cities while 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 the tour plus the penalties of the cities not in the tour. In the online version, cities are disclosed 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 show how our approach can be combined with an approximation algorithm in order to obtain an O(1)-competitive algorithm that runs in polynomial time. (C) 2008 Elsevier B.V. All rights reserved.

The online Prize-Collecting Traveling Salesman Problem

Laura L
2008-01-01

Abstract

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 cities while 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 the tour plus the penalties of the cities not in the tour. In the online version, cities are disclosed 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 show how our approach can be combined with an approximation algorithm in order to obtain an O(1)-competitive algorithm that runs in polynomial time. (C) 2008 Elsevier B.V. All rights reserved.
2008
on-line algorithms
analysis of algorithms
combinatorial problems
File in questo prodotto:
File Dimensione Formato  
R09olpctsp_ipl.pdf

non disponibili

Dimensione 123.49 kB
Formato Adobe PDF
123.49 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14086/339
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact