On the Hardness of Reoptimization with Multiple Given Solutions

Issue title: Theory that Counts: To Oscar Ibarra on His 70th Birthday

Article type: Research Article

Authors: Böckenhauer, Hans-Joachim | Hromkovič, Juraj | Sprock, Andreas

Affiliations: Department of Computer Science, ETH Zurich, Switzerland. [email protected]; [email protected]; [email protected]

Note: [] Address for correspondence: Department of Computer Science, ETH Zurich, Switzerland

Abstract: In reoptimization, we consider the following scenario: Given an instance of a hard optimization problem together with an optimal solution for it, we want to solve a locally modified instance of the problem. It has recently been shown for several hard optimization problems that their corresponding reoptimization variants remain 𝒩𝒫-hard or even hard to approximate whereas they often admit improved approximation ratios. In this paper, we investigate a generalization of the reoptimization concept where we are given not only one optimal solution but multiple optimal solutions for an instance. We prove, for some variants of the Steiner tree problem and the traveling salesman problem, that the known reoptimization hardness results carry over to this generalized setting. Moreover, we consider the performance of local search strategies on reoptimization problems. We show that local search does not work for solving TSP reoptimization, even in the presence of multiple solutions.

Keywords: Reoptimization, Steinertree, TSP, Multiple Given Solution, Hardness

DOI: 10.3233/FI-2011-528

Journal: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 59-76, 2011