Local search is one of the most fundamental and successful paradigms for designing heuristics for hard optimization problems. The main idea is to perform a search in the space of feasible solutions. During this search, a feasible solution is replaced by a better feasible solution in a suitably defined local neighborhood until a locally optimal solution is reached. A major goal in the design of local search algorithms is to avoid bad local optima. In this talk, we discuss how parameterized algorithmics can contribute to this goal via the approach of parameterized local search. Here, the idea is to avoid bad local optima by increasing the neighborhood size at the cost of increased running times. We present theoretical and experimental results to demonstrate that parameterized local search can be a valuable addition to the toolbox for the design of state-of-the-art heuristics.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne