文献类型：期刊文献

英文题名：Optimal deterministic algorithms for some variants of Online Quota Traveling Salesman Problem

作者：Yu, Wei[1];Liu, Zhaohui[1];Bao, Xiaoguang[2]

机构：[1]E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China;[2]Shanghai Ocean Univ, Coll Informat Technol, Shanghai 201306, Peoples R China

年份：2014

卷号：238

期号：3

起止页码：735

外文期刊名：EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

收录：;EI(收录号：20142417820899);WOS:【SCI-EXPANDED(收录号:WOS:000338002600007)】；

基金：The authors are grateful to the anonymous referees for their constructive comments. This research is supported by the National Natural Science Foundation of China under Grants number 11171106, 11301184 and the Nature Science Foundation of Zhejiang Province (China) under Grant No. LQ12A01011.

语种：英文

外文关键词：Traveling salesman; Quota TSP; Online algorithm; Competitive ratio

摘要：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. (C) 2014 Elsevier B.V. All rights reserved.