Michael R. Fellows
Kernelization and the Larger Picture of Practical Algorithmics, in Contemporary Context
| DATE: | Sunday, September 4, 2011 |
ABSTRACT
The natural relationship between Parameterized Complexity and heuristics has been a subject of papers and talks since the beginnings of parameterized complexity, and has been especially recognized within the WorKer kernelization community. In the Journal of Computer and System Sciences (January 2011) celebrating Richard Karp's 2008 Koyoto Prize, and elsewhere, Karp proposes a general program, closely related to the standard FPT technique of iterative compression, as a structured approach to heuristic algorithm design, for problems in computational molecular biology and genetics. This talk will discuss Karp's general program in light of the parameterized complexity framework, and survey the contemporary context of programmatic thinking about the deployment of mathematics to serve practical computing, in which pre-processing (kernelization) has, of course, both a central and a leveraged role.
Given at WorKer 2011 – The Third Workshop on Kernelization (slides are linked there).
