Algorithms for the on-line quota traveling salesman problem
Ausiello, Giorgio; Demange, Marc; Laura, Luigi; Paschos, Vangelis (2004), Algorithms for the on-line quota traveling salesman problem, in Munro, J. Ian; Chwa, Kyung-Yong, Computing and Combinatorics 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings, Springer : Berlin, p. 290-299. http://dx.doi.org/10.1007/978-3-540-27798-9_32
TypeCommunication / Conférence
Conference title10th Annual International Conference on Computing and Combinatorics (COCOON'04)
Conference cityJeju Island
Conference countryCorée du Sud
Book titleComputing and Combinatorics 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings
Book authorMunro, J. Ian; Chwa, Kyung-Yong
Series titleLecture Notes in Computer Science
Number of pages474
MetadataShow full item record
Abstract (EN)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 the 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 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 algorithm known so far for the more general On-Line TSP problem (in the homing version).
Subjects / KeywordsAlgorithms; Traveling salesman problem
Showing items related by title and author.