In this paper we consider the Recoverable Traveling Salesman Problem (TSP). Here the task is to find two tours simultaneously, such that the intersection between the tours is at least a given minimum size, while the sum of travel distances with respect to two different distance metrics is minimized. Building upon the classic double-tree method, we derive a 4-approximation algorithm for the RecoverableTSP. We also show that if the required size of the intersection between the tours is constant, a 2-approximation guarantee can be achieved, even if more than two tours need to be constructed. We discuss consequences for approximability results in the more general area of recoverable robust optimization.
翻译:在本文中,我们考虑的是可回收的旅行销售商问题(TSP)。这里的任务是同时寻找两场旅游,这样,旅游之间的交叉点至少是一个最低尺寸,而两个不同距离的距离总和则被最小化。在传统的双树方法的基础上,我们为可回收的TSP得出了一种4种通用算法。我们还表明,如果旅行之间交叉点的所需大小保持不变,即使需要建造两场以上旅游,也可以实现2种平行保证。我们讨论了在更一般的可回收的稳健优化领域取得近似效果的后果。