PIMS Distinguished Chair Lecture Series - Jianer Chen

Randomized Process of Small Unknowns and Implicitly Enforced Parameter Bounds: New Algorithmic Techniques for Parameterized Computation

Abstract: Parameterized algorithms have witnessed a tremendous growth in the last decade and have become increasingly important in dealing with NP-hard problems that arise from the world of practical computation. In this talk, after a brief review of the basic concepts in parameterized computation, we will be focused on two new algorithmic techniques that have turned out to be useful in the recent development of parameterized algorithms: randomized process of a small unknown subset of a given universal set, and implicitly enforced parameter bounds in a branch-and-search process. These techniques are simple, effective, and have led to significant improved algorithms for a number of well-known NP-hard problems.