Funding: NWO Open Competition Exact and Natural Sciences, KLEIN-2
Running Period: 2021-2025
Staff: Dr. Bodo Manthey, Prof. dr. Tjark Vredeveld (Maastricht University)
Ph.D. student: Jesse van Rhijn (UT), Ashkan Safari (Maastricht University).
ABSTRACT
Large-scale optimization problems appear in many areas, ranging from engineering over scheduling to the sciences. Unfortunately, for many optimization problems it is unlikely that we can find optimal solutions efficiently. Still, in practice often quite simple local search heuristics succeed in finding close-to-optimal solutions surprisingly quickly. This is at stark contrast to their theoretically predicted performance, which is usually very poor.
A challenge in the analysis of algorithms is to understand why simple local search heuristics show such a remarkable performance. Beyond plain curiosity, two other reasons drive our interest to understand the performance of heuristics: First, proving rigorous bounds on the performance provides stronger guarantees than experiment evaluation alone. Second, understanding precedes improving - once we understand why and when a heuristic works well and when it fails, we can exploit this to design better heuristics. Smoothed analysis is a paradigm to analyze algorithms where classical worst-case analysis fails. Although smoothed analysis is still a young field, it has proved to be a successful tool to analyze a variety of algorithms.
The goal of this project is to prove rigorous bounds on the performance of heuristics in the framework of smoothed analysis. Beyond “pure” local search algorithms, we go one step further towards rigorously analyzing algorithms used in practice by considering hybrid heuristics and metaheuristics.