|Title:||Limitations of approximation algorithms|
|Date:||January 5, 2018 (Friday)|
|Time:||4:00 p.m. - 5:00 p.m.|
|Venue:||Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong,
|Speaker:||Prof. Siu On Chan
Department of Computer Science and Engineering
The Chinese University of Hong Kong
Approximating constraint satisfaction and related problems play a central role in the theory of approximation algorithms. These approximation algorithms, such as semidefinite programs and random walks, can be applied to a wide range of other problems, including scheduling and machine learning. In this talk, we mention recent results about the limitations of common approximation algorithms. This will reveal the complexity of many approximation problems and hopefully hint at better approximation algorithms for other problems.
Prof. Siu On Chan got his BEng from The Chinese University of Hong Kong, MSc from University of Toronto, and PhD from UC Berkeley. He then worked as a postdoc researcher at Microsoft Research New England. He is an Assistant Professor at the Department of Computer Science and Engineering, The Chinese University of Hong Kong. He won Best Paper Award and Best Student Paper Award at STOC 2013.
Enquiries: Ms. Crystal Tam at tel. 3943 8439
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar.