The Lost Continent of Polynomial Time: Preprocessing and Kernelization

摘要

One of the main objectives of the talk is to survey the history of the practical algorithmic strategy of preprocessing (also called data-reduction and kernelization) since the beginnings of computer science, and to overview what theoretical computer science has been able to say about it.