The Chinese University of Hong Kong
Department of Computer Science and Engineering

Seminar

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,
Shatin, N.T.
Speaker: Prof. Siu On Chan
Assistant Professor
Department of Computer Science and Engineering
The Chinese University of Hong Kong

 

ABSTRACT:

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.

 

BIOGRAPHY:

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.

 

**** ALL ARE WELCOME ****