| Current Trends in Theory and Practice of Computer Science |
| Home |
 |
|
|
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. |
| SOFSEM 2008, January 19-25, High Tatras, Slovakia |