A Survey on Online Bipartite Matching and Its Generalizations

PhD Qualifying Examination


Title: "A Survey on Online Bipartite Matching and Its Generalizations"

by

Mr. Yuchen MAO


Abstract:

Bipartite matching is a fundamental problem in combinatorial optimization. 
Its online version has lots of applications such as matching requests to 
servers, items to bidders, and ads to advertisers. In this survey, we will 
study the online bipartite matching problem and its four generalizations 
in two input models - the adversarial model and the random arrival model. 
We will review the current best algorithms, their analyses, as well as the 
hardness results for these problems.


Date:			Wednesday, 11 February 2015

Time:                  	10:00am - 12:00noon

Venue:                  Room 3494
                        Lifts 25/26

Committee Members:	Prof. Siu-Wing Cheng (Supervisor)
 			Prof. Cunsheng Ding (Chairperson)
 			Dr. Sunil Arya
 			Dr. Ke Yi


**** ALL are Welcome ****