On One Approach to TSP Structural Stability

In this paper we study an inverse approach to the traveling salesman reoptimization problem. Namely, we consider the case of the addition of a new vertex to the initial TSP data and fix the simple “adaptation” algorithm: the new vertex is inserted into an edge of the optimal tour. In the paper we consider the conditions describing the vertexes that can be inserted by this algorithm without loss of optimality, study the properties of stability areas, and address several model applications. 1. Introduction Stability of the traveling salesman problem (TSP) has been studied from the 1970s [1, 2] in case the weight matrix is subject to perturbation. This work was continued in a much more general way [3–9]. Another approach to the stability of the TSP is connected with the master tour property [10, page 435] with the key result [11]. At last there is the reoptimization [12, 13] approach to face the case where the weight matrix remains undisturbed while the number of cities varies (with the correspondent variation of the weight matrix size). Usually, reoptimization of NP-hard problems is NP-hard. Even if the optimal solution of the initial instance is known for free, the reoptimization remains NP-hard [14]. Moreover, the situation is not improved if all optimal solutions are known [15]. In this work we consider the following inverse reoptimization problem: we fix an “adaptation” algorithm and study what distortions of the initial data may be “adapted” by this algorithm. Specifically, we consider the conditions under which a new city may be inserted between two consequent cities of an optimal tour without loss of optimality. Sufficient condition is always polynomial; however necessary and sufficient conditions are only polynomial if the solution of the initial instance and the solutions of some “close” instances are provided by an oracle. These results sharpen the previous author’s work on TSP adaptive stability [16, 17] (in Russian) for “open-ended” tours which is a special case of the general approach to the adaptive stability of discrete optimization problems [18, chapter 1] (in Russian). 2. Designations and Definitions Let us restrict all possible TSP cities to the elements of a finite set and introduce a cost function . For each initial set of cities we fix the set of permutations . Henceforth we associate the elements of with the circular tours on , supposing the existence of the additional edge . The cost of a circular tour is naturally defined as A tour is called optimal over if The insertion of a new city into an existing tour after the city gives the