Satellite workshop of MFCS 2019 at RWTH Aachen on August 30, 2019

Registration and Program

Registration to ARDA can be done through the MFCS website; it is possible to register to ARDA only. The program consists of the following ten invited talks.

Session 1: Reoptimization
14:05Tobias Mömke: Robustness in reoptimization (abstract)
14:30Davide Bilò: New algorithms for Steiner tree reoptimization (abstract)
14:55Hans-Joachim Böckenhauer, Elisabet Burjons Pujol, Martin Raszyk, and Peter Rossmanith: Reoptimization of parameterized problems (abstract)
15:20Coffee break
Session 2: Dynamic Algorithms and Neighborly Help
15:45Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams: Dynamic parameterized problems and algorithms (abstract)
16:10Fabian Frei and Rodrigo Ronald Gumucio Escobar: Makespan scheduling with neighborly help (abstract)
16:35Faisal Abu-Khzam, Cristina Bazgan, and Henning Fernau: Dynamic variants of red-blue dominating set (abstract)
17:00Davide Bilò: The All-Best-Swap-Edge problem on tree spanners (abstract)
17:25Coffee break
Session 3: Reconfiguration and Temporal Graphs
17:45Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche: Multistage vertex cover (abstract)
18:10Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob Spooner: Two moves per time step make a difference (abstract)
18:35Dennis Fischer and Janosch Fuchs: Color reconfiguration with token swapping (abstract)

Call for Papers

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,

The goal of this workshop is to bring together researchers from various areas related to reoptimization and dynamic algorithms.

Programm Committee

Important Dates