Operational Parameterization for Heuristics (OPERAH)

• Applicant: Professor Dr. Christian Komusiewicz
• Subject Area: Theoretical Computer Science
• Term: from 2019 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 428493315

Many computational problems arising in practice are NP-hard. It is thus conjectured that these problems cannot be solved efficiently on all input instances. A theory-driven approach to algorithm design for hard problems is parameterized algorithmics. Here, the aim is to obtain efficient algorithms by exploiting the structure of typical input data. This structure is described by a numerical parameter depending on the input data. Parameterized algorithms are then fast on those inputs where the parameter has a small value. Parameterized algorithms may lead to state-of-the art implementations for some problems. Nevertheless, they are seldom used in practice where heuristics are the method of choice. Two very important heuristic approaches are local search and greedy heuristics.The project Operational Parameterization for Heuristics (OPERAH) aims at understanding how parameterized algorithms can be used to further improve local search and greedy heuristics. The focal point of the studies are so-called operational parameters. These are not determined by input structure but rather chosen by the user of the algorithms. Operational parameters describe a trade-off between higher running times and better solution quality: increasing the parameter value improves the solution while increasing the running time. Thus, the user limits the running time by choosing the parameter value and obtains a solution of the corresponding quality.With this type of parameterization, we aim to mitigate a drawback of parameterized algorithms, the fact that real-world input data often has large parameter values for classic parameters. In this way, we aim to increase the practical potential of parameterized algorithmics. More concretely, the aim is to study the paradigm of operational parameterization for several important optimization problems. For each, the goal is to either develop efficient algorithms for parameterized local search or the so-called turbocharging of greedy heuristics or to show that such algorithms contradict standard conjectures in computer science. The developed algorithms will be implemented and compared experimentally with state-of-the-art heuristics. In these studies, we particularly aim at assessing the above-mentioned trade-off between running time and solution quality.

• DFG Programme: Research Grants