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.
| 14:00 | Opening |
| Session 1: Reoptimization (Chair: Henning Fernau) | |
| 14:05 | Tobias Mömke: Robustness in reoptimization (abstract) |
| 14:30 | Davide Bilò: New algorithms for Steiner tree reoptimization (abstract) |
| 14:55 | Hans-Joachim Böckenhauer, Elisabet Burjons Pujol, Martin Raszyk, and Peter Rossmanith: Reoptimization of parameterized problems (abstract) |
| 15:20 | Coffee break |
| Session 2: Dynamic Algorithms and Neighborly Help (Chair: Thomas Erlebach) | |
| 15:45 | Josh Alman, Matthias Mnich, and Virginia Vassilevska Williams: Dynamic parameterized problems and algorithms (abstract) |
| 16:10 | Fabian Frei and Rodrigo Ronald Gumucio Escobar: Makespan scheduling with neighborly help (abstract) |
| 16:35 | Faisal Abu-Khzam, Cristina Bazgan, and Henning Fernau: Dynamic variants of red-blue dominating set (abstract) |
| 17:00 | Davide Bilò: The All-Best-Swap-Edge problem on tree spanners (abstract) |
| 17:25 | Coffee break |
| Session 3: Reconfiguration and Temporal Graphs (Chair: Tobias Mömke) | |
| 17:45 | Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche: Multistage vertex cover (abstract) |
| 18:10 | Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob Spooner: Two moves per time step make a difference (abstract) |
| 18:35 | Dennis Fischer and Janosch Fuchs: Color reconfiguration with token swapping (abstract) |
| 19:00 | End |
Impressions
 Tobias Mömke |
 Elisabet Burjons |
 Henning Fernau |
 Davide Bilò |
 Thomas Erlebach |
 Dennis Fischer |
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,
- 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.
Programm Committee
- Faisal Abu-Khzam (Lebanese American University Beirut)
- Davide Bilò (University of Sassari)
- Hans-Joachim Böckenhauer (ETH Zürich, co-chair)
- Thomas Erlebach (University of Leicester)
- Henning Fernau (University of Trier)
- Dennis Komm (ETH Zürich, co-chair)
- Matthias Mnich (University of Bonn)
- Tobias Mömke (Saarland University)
- Rolf Niedermeier (Technical University of Berlin)
- Vangelis Paschos (University Paris-Dauphine)
- Hadas Shachnai (Technion)
Important Dates
- Submission Deadline July 5, 2019
- Notification of Acceptance July 14, 2019
- Workshop August 30, 2019