报告题目：An Introduction to Fixed-Parameter Tractable Algorithms
At this point, if an optimization problem is NP-complete it is likely that one has to spend exponential time to solve the problem exactly. In reality, people typically use approximation algorithms to handle NP-complete problems, but in many applications an approximate solution is not good enough. FPT algorithms give people a way to solve some NP-complete problems exactly in polynomial time, when the solution value is small. In this talk, I will introduce FPT algorithms through a problem called MSR, which originates from computational biology.
报告题目：Geometric Facility Location
Many problems in facility location can be embedded in Euclidean spaces.Classical problems are Euclidean k-center and Euclidean k-median. We will discuss algorithms developed for these problems and their variations - discrete case, different metrics, competitive facility location.