Algorithms for Combinatorial Reoptimization

Gal Tamir (Ph.D. Thesis Seminar)

Wednesday, 06.01.2016, 15:30

Taub 601

Advisor: Prof. H. Shachnai

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.