Combinatorial optimization plays an important role in AI and real life. However, many optimization problems are NP hard, that is to say, there is no polynomial-time algorithm for them under reasonable assumptions. In practice, we have designed fast heuristic algorithms and exact algorithms for many of these problems, and they have a very good performance on tested benchmark instances. On the other hand, theoretical algorithms, may not be so practical, solve the problems with theoretical guarantees of running-time bound and solution quality, etc. In this talk, I will discuss the differences between theoretical and practical algorithms, and take the maximum independent set problem as an example to introduce exact algorithms with theoretical running-time bounds.
