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 -