TY - JOUR

T1 - A Theory and Algorithms for Combinatorial Reoptimization

AU - Schieber, Baruch

AU - Shachnai, Hadas

AU - Tamir, Gal

AU - Tamir, Tami

N1 - Funding Information:
A preliminary version of this paper appeared in the Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN), Arequipa, April 2012. Research supported by the Israel Science Foundation (Grant Number 1574/10), and by the Ministry of Trade and Industry MAGNET program through the NEGEV Consortium.
Funding Information:
This work was partly carried out during a visit of the second author to DIMACS supported by the National Science Foundation under Grant Number CCF-1144502. Work partially supported also by the Technion V.P.R. Fund, and by the Smoler Research Fund. We thank Rohit Khandekar and Viswanath Nagarajan for stimulating discussions on the paper.
Publisher Copyright:
© 2017, Springer Science+Business Media New York.

PY - 2018/2/1

Y1 - 2018/2/1

N2 - 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 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 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. Using our 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 introduced by Woeginger (Proceedings of Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999), a (1, 3)-reapproximation algorithm for the metric k-Center problem, 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 the objective of minimizing transition costs, while guaranteeing a good approximation for the underlying optimization problem.

AB - 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 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 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. Using our 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 introduced by Woeginger (Proceedings of Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999), a (1, 3)-reapproximation algorithm for the metric k-Center problem, 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 the objective of minimizing transition costs, while guaranteeing a good approximation for the underlying optimization problem.

KW - Approximation schemes

KW - Combinatorial reoptimization

KW - Reapproximation

KW - Subset selection

KW - k-Center

UR - http://www.scopus.com/inward/record.url?scp=85010837013&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85010837013&partnerID=8YFLogxK

U2 - 10.1007/s00453-017-0274-8

DO - 10.1007/s00453-017-0274-8

M3 - Article

AN - SCOPUS:85010837013

SN - 0178-4617

VL - 80

SP - 576

EP - 607

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -