2012 | OriginalPaper | Chapter
A Theory and Algorithms for Combinatorial Reoptimization
Authors : Hadas Shachnai, Gal Tamir, Tami Tamir
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.