Ph.D Student | Tamir Gal |
---|---|

Subject | Algorithms for Combinatorial Reoptimization |

Department | Department of Computer Science |

Supervisor | Professor Hadas Shachnai |

Full Thesis text |

This work aims to better model the dynamic nature of real-life applications in which the goal is to maximize (or minimize) certain objective function. 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 may incur some cost, a natural goal is to

have the solution for the new instance
*close* to the original one (under a certain distance measure).

We first study a reconfiguration
problem arising in storage area network, where files are placed on a set of
servers. Each server has a storage capacity and a load capacity. We seek to minimize
the cost of moving from one file configuration to another, following the
frequent changes in demands for these files. This may require moving files from
one server to another, as well as modifying the load capacity allocated to each
file. We present algorithms that achieve the optimal cost by using servers
whose load capacities are increased by *O(1)*.

Motivated by this natural real-life
scenario, we then 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, for some *r*,
ρ ≥ 1, we say that *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 *r* = ρ =1, we call *A*
a reoptimization algorithm.

In this model we derive
reoptimization and reapproximation algorithms for several classes of
combinatorial reoptimization problems. This includes a fully polynomial time (1ε_{1},
1ε_{2}) -reapproximation scheme for the wide class of
DP-benevolent problems, a (1,6)-reapproximation algorithm for the metric k-Center
problem, and a reoptimization algorithm for polynomially solvable
subset-selection problems.

We further show that our results can
be extended 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.