A Theory and Algorithms for Combinatorial Reoptimization

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

${\cal A}$

is an (

r

,

ρ

)-reapproximation algorithm if it achieves a

ρ

-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

ρ

 = 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.