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.
Short CV
Rolf Niedermeier studied Computer Science with Mathematics at TU München. He received his PhD and his habilitation from the University of Tübingen. From 2004 to 2010 he was a professor of Theoretical Computer Science at Friedrich-Schiller-University Jena and since 2010 he leads the Algorithmics and Computational Complexity group at TU Berlin. Since more than 15 years his research is centering around ways to understand and cope with computational hardness, with a special focus on 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” (Oxford University Press 2006). He is an associate editor of the journals “Discrete Mathematics and Theoretical Computer Science” and “Journal of Computer and System Sciences”. Since 2016, he is a member of the DFG review board (one of four members representing Theoretical Computer Science).
