UM scholar's study on online matching published by top journal of ACM
21 May 2020
In a study on online matching, a scholar at the University of Macau (UM) has discovered a new model that can be widely used in today's society, such as in the DiDi carpooling service, or landlord and tenant matching. The study is the only breakthrough in arbitrary online matching problems in the past 30 years. The related paper has been published by the Association for Computing Machinery's (ACM) top journal Journal of the ACM. It is also the first paper from Macao that has been published in the journal in the past decade.
Titled ‘Fully Online Matching’, the paper is written by Wu Xiaowei, an assistant professor in the Department of Computer and Information Science, Faculty of Science and Technology, who is also a member of the State Key Laboratory of Internet of Things for Smart City. The paper has been published in the latest issue of the Journal of the ACM, which is considered a top journal in the field of theoretical computer science that only publishes papers with a profound impact on the field. In the past decade, the journal has published less than 400 articles, of which only 15 come from China (including Hong Kong, Macao, and Taiwan).
Based on an article presented by the Turing Award winner Karp et al at the ACM Symposium on Theory of Computing 1990, Prof Wu’s paper serves as an extension of the article’s online bipartite matching problem. By extending the classic KVV model to any (non-binary) graph and allowing all points to appear online, the study has discovered a new model that will have many applications in today's society, such as DiDi carpooling service as well as landlord and tenant matching, where KVV models are not applicable. The study has also proposed several theoretical guarantees for this kind of problems and has become the only breakthrough in arbitrary online matching problems proposed by Karp et al in the past 30 years.
Prof Wu obtained his PhD degree in computer science from the University of Hong Kong in 2015 and later worked as a postdoctoral fellow at the University of Vienna. His research interests include computer science theory, online algorithms, approximation algorithms, dynamic data structure, urban big data, and intelligent technologies.
澳大科技學院電腦及資訊科學系助理教授及智慧城市物聯網國家重點實驗室成員吳曉偉的論文《全面線上配對》（Fully Online Matching）發表在最新一期的ACM期刊。該期刊只登載那些對計算機科學有深遠影響的論文，過去十年總收錄文章不足400篇，其中15篇來自中國（包括港澳台）地區，是公認的理論計算機科學領域中最頂尖的期刊。