Summary: In the online version of Travelling Salesman Problem, requests to the server (salesman) may be presented in an online manner i.e. while the server is moving. In this paper, we consider a special case in which requests are located only on the circumference of a circle and the server moves only along the circumference of that circle. We name this problem as online Travelling Salesman Problem on a circle (OLTSP-C). Depending on the minimization objective, we study two variants of this problem. One is the homing variant called H-OLTSP-C in which the objective is to minimize the time to return to the origin after serving all the requests. The other is the nomadic variant called N-OLTSP-C in which after serving all the requests, it is not required to end the tour at the origin. The objective is to minimize the time to serve the last request. For both the problem variants, we present online algorithms and lower bounds on the competitive ratios. An online algorithm is said to be zealous if the server that is used by the online algorithm does not wait when there are unserved requests. For N-OLTSP-C, we prove a lower bound of \(\frac{28}{13}\) on the competitive ratio of any zealous online algorithm and present a 2.5-competitive zealous online algorithm. For H-OLTSP-C, we show how the proofs of some of the known results of OLTSP on general metric space and on a line metric, can be adapted to get lower bounds of \(\frac{7}{4}\) and 2 on the competitive ratios of any zealous and non-zealous online algorithms, respectively.
For the entire collection see [Zbl 1408.68017].