Parameterized Algorithmics meets Programming by Optimization - Parameter-Sensitive Algorithm Deployment For Real-World Instances

• Applicant: Dr. Sepp Hartung
• Subject Area: Theoretical Computer Science
• Term: Funded in 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 258946267

Parameterized algorithmics deals with the development of exact algorithms for (NP-)hard computational problems.Specifically, each of the corresponding FPT-algorithms (fixed-parameter tractable) is designed for a certain problem parameter and is efficient on instances where the parameter is small.Many parameters measure the distance of an instance to an efficiently solvable special case.For example, many graph problems are efficiently solvable on special graphs such as trees.Unfortunately, practical instances typically will not be trees, motivating parameters which measure the distance from trees.Thus, the corresponding FPT-algorithm is efficient for "tree-like" inputs.A main motivation of parameterized algorithmics is to understand the "unexplained success of heuristic algorithms" and to exploit the gained insights for the development of exact algorithms.Heuristics may fail to compute optimal solutions on some instances, but these "hard" instances seldomly occur in practical settings.A widely accepted explanation for this is that practical instances admit a certain structure (e.g. being close to trees) which is exploited by heuristics.Parameterized algorithmics strives for measuring these structures in terms of structural parameters.This project aims to consider the potential of FPT-algorithms for exactly solving practical instances while being competitive to heuristics in terms of running times.In this way we examine whether the prominent concept of studying structural parameters is able to "discover" those structures that are responsible for the unexplained success of heuristics.When developing these algorithms one faces the problem to choose, based on the parameter values of a concrete instance, the most efficient FPT-algorithm.This choice is additionally complicated by the fact that usually there are many variants of an FPT-algorithm. Additionally, FPT-algorithms can be typically freely combined with the application of data reduction rules, the computation of lower bounds, etc..Hence, there are usually many variants and configurations of an FPT-algorithm, each having a poorly understood impact.To address these challenges, the method of "Programming by Optimization" (PbO) will be applied.When creating programs, PbO aims to avoid premature commitment on the design of the algorithm and encourages software developers to use certain generic programming language extensions to provide interchangeable code parts.By using appropriate programming tools, the program then gets automatically optimized for solving a given set of problem instances.PbO has been successfully applied to optimize solvers for NP-hard problems like"Mixed integer programming"and "Propositional Satisfiability".By studying four concrete problems this project attempts to show that PbO can be also applied to optimize the deployment of FPT-algorithms in order to be competitive with heuristics while solving the problem (provably) exactly.

• DFG Programme: Research Fellowships
• International Connection: Canada
• Host: Professor Dr. Holger Hoos