Doctoral Prize
 LAP CHI LAU, The Chinese University of Hong Kong
On approximate minmax theorems for graph problems
[PDF] 
Minmax theorems are basic results in graph theory, and are useful in designing polynomial time algorithms for graph problems. However, many graph problems are NPhard, and thus minmax theorems and polynomial time algorithms do not exist under some wellknown complexity assumptions. Recent research has focused on designing polynomial time approximation algorithms for these NPhard graph problems. In this talk, we will present some graph theoretical approximate minmax theorems, which can be used to obtain polynomial time approximation algorithms for NPhard graph problems. Also, we will show the applications of these results to a data transmission problem in computer networks.
