Fully dynamic maximal independent set with sublinear update time
Sepehr Assadi, Baruch Schieber, et al.
STOC 2018
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.
Sepehr Assadi, Baruch Schieber, et al.
STOC 2018
Baruch Schieber, Uzi Vishkin
Discrete Applied Mathematics
Rohit Khandekar, Baruch Schieber, et al.
FSTTCS 2010
Allan Borodin, Sandy Irani, et al.
STOC 1991