Algorithms for the on-line quota traveling salesman problem

Algorithms for the on-line quota traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20073131
Country: Netherlands
Volume: 92
Issue: 2
Start Page Number: 89
End Page Number: 94
Publication Date: Oct 2004
Journal: Information Processing Letters
Authors: , , ,
Keywords: orienteering
Abstract:

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 given quota of sales, minimizing the amount of time. In this paper we address the on-line version of the problem, where requests are given over time. We present algorithms for various metric spaces, and analyze their performance in the usual framework of competitive analysis. In particular we present a 2-competitive algorithm that matches the lower bound for general metric spaces. In the case of the halfline 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 algorithm known so far for the On-Line TSP (in the homing version).

Reviews

Required fields are marked *. Your email address will not be published.