报告题目：Fully Online Matching
报 告 人：张宇昊（香港大学 博士）
报告时间：2020年12月4日 下午2:00开始
报告地点：腾讯会议ID：482 962 4974；密码：485075
报告摘要：We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors’ arrivals. If a vertex remains unmatched until its deadline, then the algorithm must irrevocably either match it to an unmatched neighbor or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, and so on. We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step toward solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, then we show a tight competitive ratio ≈0.5671 of Ranking. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 < 1- 1/e-competitive in our model, even for bipartite graphs.
报告人简介：张宇昊，从事组合优化研究，研究方向是在线算法以及近似算法，主要研究工作集中于在线匹配问题，在线调度问题，以及斯坦纳树问题。2020年博士毕业于香港大学计算机科学专业，导师为黄志毅博士，期间曾于2018年8~11月在上海财经大学理论计算机研究中心访问。在此之前，张宇昊本科毕业于浙江大学，并参加张国川教授的组合优化研究小组，进行相关方面的研究。张宇昊的研究成果多次发表于理论计算机领域的主流期刊和顶级会议《J.ACM》、《TALG》、《STOC》、《FOCS》、《SODA》、《ICALP》、《APPROX》。
