Speaker: Dr. Hubert Chan

Title: Analyzing Oblivious Matching Problem on Arbitrary Graphs

时间：3月13日（周四）  16:00- 17:00

地点：海韵校区行政楼C410

Abstract.

In this talk, we revisit the well-known oblivious matching problem on general graphs, in which an adversary fixes a graph whose edges are oblivious to the algorithm. We analyze the famous Ranking algorithm, and describe the mathematical techniques used to analyze the problem.

Of particular interest is a continuous linear program relaxation that can give a performance ratio 0.523.

Bio:

Dr Hubert Chan is currently an Assistant Professor at the Department of Computer Science at the University of Hong Kong. He completed his PhD in Computer Science at Carnegie Mellon University in 2007.  Before taking up the faculty position at HKU, he spent two years as a post-doc at Max-Planck-Institut fuer Informatik in Germany.  His main research interests are approximation algorithms, discrete metric space, privacy and security inspired problems.