Many practically relevant situations require to solve not only one singular instance of an optimization problem, but a sequence of them. This naturally gives rise to the question of whether the knowledge of a good solution for one instance can be used for facilitating the computation of a good solution for a related instance. Consider, for instance, the maintenance of a train schedule. In case of some local modification, e.g., a station closing down or being newly opened, we do not want to compute a new schedule from scratch, but we want to make use of the old schedule.
Problems like these have been considered from various viewpoints under various names. Analyzing one step of local modification (or sometimes a short sequence of steps) with respect to approximability of a hard optimization problem has been considered under the name of reoptimization. Conversely, dynamic data structures and dynamic algorithms consider an arbitrary sequence of modifications for some (not necessarily hard) problem.
There are many recent approaches bringing substantially new ideas to this field, for example,
new techniques to design PTASs for reoptimization problems,
robust reoptimization, i.e., making use of approximate solutions for neighboring instances, thus enabling the analysis of multi-step reoptimization,
constrained reoptimization, i.e., finding new solutions that are similar to the given old solution,
reoptimization in the presence of multiple given solutions to one or more related instances,
dynamic algorithms computing exact solutions in the framework of parameterized algorithmics.
The goal of this workshop is to bring together researchers from various areas related to reoptimization and dynamic algorithms.
