Prof. Dr. Rolf Niedermeier from TU Berlin is one of the world-wide leading experts in parameterized and multivariate algorithm design and analysis. He is co-author of more than 100 journal articles and more than 120 peer-reviewed conference papers and of the monograph “Invitation to Fixed-Parameter Algorithms”. He will give a talk about "Parameterized Algorithmics - On Interactions with Heuristics" in the HPI Colloquium.

Where: Hörsaal 1, HPI

When: Thursday, November 10, 2016, 16:00

Title: Parameterized Algorithmics - On Interactions with Heuristics

Abstract: Parameterized algorithm design is mainly tailored towards identifying “tractable” special cases for “intractable” (that is, typically NP-hard) problems. Ideally, this leads to efficient algorithms providing optimal solutions. The central observation herein is that if some problem-specific parameters are small, then certain problems can be solved efficiently by confining exponential running time growth to the parameters only. In real-world scenarios, most computationally hard problems are attacked with heuristic approaches, that is, often simple (in particular, greedy) algorithms that are efficient but do not guarantee optimal solutions, or algorithms without provable running time guarantees. As Richard Karp pointed out, a long-term goal of Theoretical Computer Science is to contribute to a better understanding of the effectiveness of heuristics. In this talk, through some case studies including examples from graph-based data clustering, graph anonymization, and computational social choice, we discuss some fruitful interactions between heuristics and parameterized algorithm design and analysis.

Links:Official announcement, Video of the talk