Wednesday, May 15, 2019

[DMANET] Call for Papers: Advances in Reoptimization and Dynamic Algorithms 2019

Advances in Reoptimization and Dynamic Algorithms
ARDA 2019 — Satellite workshop of MFCS 2019 at RWTH Aachen on August 30, 2019

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. There will be no formal proceedings, thus talks about already published results or ongoing work are very welcome. Submissions are expected to be two-page abstracts.


* 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)


* Submission Deadline June 30, 2019
* Notification of Acceptance July 14, 2019
* Workshop August 30, 2019
* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.