Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
479660 | European Journal of Operational Research | 2014 | 6 Pages |
Abstract
•We examine various variants of the Online Quota Traveling Salesman Problem.•The best lower bounds and algorithms for the variants are obtained.•We get a nearly complete map of the optimal algorithms for variants of Online QTSP.•A best lower bound for a variant of Online TSP on a half-line is also obtained.
This paper is concerned with the Online Quota Traveling Salesman Problem. Depending on the symmetry of the metric and the requirement for the salesman to return to the origin, four variants are analyzed. We present optimal deterministic algorithms for each variant defined on a general space, a real line, or a half-line. As a byproduct, an improved lower bound for a variant of Online TSP on a half-line is also obtained.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Wei Yu, Zhaohui Liu, Xiaoguang Bao,