Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights

摘要

We consider the following optimization problem: Given an instance of an optimization problem and some optimum solution for this instance, we want to find a good solution for a slightly modified instance. Additionally, the scenario is addressed where the solution for the original instance is not an arbitrary optimum solution, but is chosen amongst all optimum solutions in a most helpful way. In this context, we examine re-optimization of the travelling salesperson problem, in particular MinTSP and MaxTSP as well as their corresponding metric versions. We study the case where the weight of a single edge is modified. Our main results are the following: existence of a 4/3-approximation for the metric MinTSP-problem, a 5/4-approximation for MaxTSP, and a PTAS for the metric version of MaxTSP.