28.6. 13:00 - On the Complexity of Restarting

Universität Ulm

Restarting is a technique used by many randomized local search and systematic search algorithms. If the algorithm has not been successful for some time, the algorithm is reset and reinitialized with a new random seed. However, for some algorithms and some problem instances, restarts are not beneficial.

New results regarding the complexity of deciding whether restarting is beneficial are presented, including the NP-hardness of the problem, and the non-existence of an approximation algorithm for the optimal restart time.

This talk is held in preparation for the presentation of the results at CSR 2019.