Centre de recherches mathématiques

Fields Institute


Pacific Institute for the Mathematical Sciences

University of Western Ontario
Université Western Ontario
Département de mathématiques
Faculté d'éducation
Faculté des sciences
Recherche Western
Département de mathématiques appliquées

Nous remercions chaleureusement ces commanditaires de leur soutien.

Prix de doctorat

LAP CHI LAU, The Chinese University of Hong Kong
On approximate min-max theorems for graph problems

Min-max theorems are basic results in graph theory, and are useful in designing polynomial time algorithms for graph problems. However, many graph problems are NP-hard, and thus min-max theorems and polynomial time algorithms do not exist under some well-known complexity assumptions. Recent research has focused on designing polynomial time approximation algorithms for these NP-hard graph problems. In this talk, we will present some graph theoretical approximate min-max theorems, which can be used to obtain polynomial time approximation algorithms for NP-hard graph problems. Also, we will show the applications of these results to a data transmission problem in computer networks.