Many real-life applications involve systems that change dynamically
over time. Thus, throughout the continuous operation of such
a system, it is required to compute solutions for new problem instances,
derived from previous instances. Since the transition from one solution
to another incurs some cost, a natural goal is to have the solution for the
new instance close to the original one (under a certain distance measure).
In this paper we develop a general model for combinatorial reoptimization,
encompassing classical objective functions as well as the goal of
minimizing the transition cost from one solution to the other. Formally,
we say that A is an (r, \rho)-reapproximation algorithm if it achieves a \rho-
approximation for the optimization problem, while paying a transition
cost that is at most r times the minimum required for solving the problem
optimally. When \rho = 1 we get an (r,1)-reoptimization algorithm.
Using our model we derive reoptimization and reapproximation algorithms
for several important classes of optimization problems. This includes
fully polynomial time reapproximation schemes for DP-benevolent
problems, a class introduced by Woeginger (Proc. Tenth ACM-SIAM
Symposium on Discrete Algorithms, 1999), reapproximation algorithms
for metric Facility Location problems, and (1,1)-reoptimization algorithm
for polynomially solvable subset-selection problems.
Thus, we distinguish here for the first time between classes of reoptimization
problems, by their hardness status with respect to minimizing
transition costs while guaranteeing a good approximation for the underlying
optimization problem.