Algorithms for the On-Line Quota Traveling Salesman Problem
5,00 €
     
SINTESI
The Quota Traveling Salesman Problem is a generalization of the well known Traveling Salesman Problem. The goal of the traveling salesman is, in this case, to reach a giiven quota of the sales, minimizing the amount of time, In this paper we address the on-line version od the problem, where requests are given over time. We presents algorithms for various metric spaces, and analyze their performance in the usual framework of the competitive analysis. In particular we present a 2-competitive algorithm that matches the lower bound for general metric spaces. In the case of the half-line metric space, we show that it is helpful not to move at full speed, and this approach is also used to derive the best on-line polynomial time algorith, known so ar for the more general on line TSO problem (in the homing version)
pagine: 16
formato: 17 x 24
ISBN: 978-88-7999-692-1
data pubblicazione: Gennaio 2006
editore: Aracne
collana: Dipartimento di Informatica e Sistemistica “Antonio Ruberti” della “Sapienza” Università di Roma | 2004/2
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