The Taub Faculty of Computer Science Events and Talks

Traditional combinatorial optimization problems require finding solutions for a single problem instance. However, 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. Moreover, 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 certain distance measure). In this work, we develop a general framework for combinatorial repotimization, encompassing classical objective functions as well as the goal of minimizing the transition cost from one solution to the other. Formally, we say that ALG is an (r,p)-reapproximation algorithm if it achieves a p-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 p = 1 we get an (r,1)-reoptimization algorithm. Using our model we derive reoptimization and reapproximation algorithms for several classes of combinatorial reoptimization problems, including the wide class of DP-benevolent problems, metric k-Center, and polynomially solvable subset-selection problems. We extend these results to the reoptimization variants of subset selection problems that are known to be NP-hard, such as real-time scheduling and the maximum generalized assignment problem (GAP), via a non-standard use of Lagrangian relaxation of the underlying optimization problems.