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.
28.6. 13:00 - On the Complexity of Restarting
Uwe Baier 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.