论文标题
与已知位置的在线TSP
Online TSP with Known Locations
论文作者
论文摘要
在本文中，我们考虑了在线旅行销售人员问题（OLTSP），该问题已提前知道请求的位置，但他们的到达时间却不知道。我们研究了两个开放式变体，其中算法不需要在提供所有请求以及封闭式变体时返回原点，在该变体中，算法在服务所有请求后必须返回原点。我们的目的是衡量位置额外知识对问题竞争力的影响。我们为一般案例提供了一种在线3/2竞争算法，开放式和封闭式变体的匹配下限。然后，我们专注于一些有趣的度量空间（环，星，半线），为问题提供下限和多项式时间在线算法。
In this paper, we consider the Online Traveling Salesperson Problem (OLTSP) where the locations of the requests are known in advance, but not their arrival times. We study both the open variant, in which the algorithm is not required to return to the origin when all the requests are served, as well as the closed variant, in which the algorithm has to return to the origin after serving all the requests. Our aim is to measure the impact of the extra knowledge of the locations on the competitiveness of the problem. We present an online 3/2-competitive algorithm for the general case and a matching lower bound for both the open and the closed variant. Then, we focus on some interesting metric spaces (ring, star, semi-line), providing both lower bounds and polynomial time online algorithms for the problem.
