**Invited Talk**

Foundations of Computer Science

Thursday, January 24, 10:30 - 12:00

Juraj Hromkovič

(with Hans-Joachim Böckenhauer, Tobias Mömke, and Peter Widmayer)

*On the Hardness of Reoptimization*

We consider the following scenario of reoptimization: Given an
instance of an optimization problem together with an optimal solution,
we want to find a high-quality solution for a locally modified
instance. The naturally arising question is whether the knowledge of
an optimal solution to the unaltered instance can help in solving the
locally modified instance.

Using some variants of the traveling salesman problem and the Steiner
tree problem as examples, we show that the answer to this question
depends on the considered problem and the type of local modification and
can be totally different: For instance, for some reoptimization
variant of the metric TSP, we get a *1.4*-approximation improving on
the best known approximation ratio of *1.5* for the classical metric
TSP. For the Steiner tree problem on graphs with bounded cost
function, which is APX-hard in its classical formulation, we even
obtain a PTAS for the
reoptimization variant. On the other hand, for a variant of TSP, where
some vertices have to be visited before a prescribed deadline, we are
able to show that the reoptimization problem is exactly as hard to
approximate as the original problem.