טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentTamir Gal
SubjectAlgorithms for Combinatorial Reoptimization
DepartmentDepartment of Computer Science
Supervisor Professor Hadas Shachnai
Full Thesis textFull thesis text - English Version


Abstract

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.