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

• DOI: 10.1016/j.ejor.2014.04.037
• Publication Date: 2014-05-09T07:46:19Z
• Authors: Wei Yu; Zhaohui Liu; Xiaoguang Bao
• Keywords: Traveling purchaser problem

Abstract 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.