Optimal deterministic algorithms for some variants of Online Quota Traveling Salesman Problem

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.

MoreLess

Year of publication:	2014
Authors:	Yu, Wei ; Liu, Zhaohui ; Bao, Xiaoguang
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 238.2014, 3, p. 735-740
Publisher:	Elsevier
Subject:	Traveling salesman \| Quota TSP \| Online algorithm \| Competitive ratio

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10010785317