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.
Source: Faculty of Science and Technology
Media Contact Information:Communications Office, University of Macau
Albee Lei Tel：(853) 88228004Judite Lam Tel：(853) 88228022Email：prs.media@um.edu.moUM Website：www.um.edu.mo
