UM scholar's study on online matching published by top journal of ACM
澳大學者研究在線匹配有突破性進展 獲國際頂尖ACM期刊刊登

21 May 2020

Wu Xiaowei
吳曉偉

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.

澳門大學學者一項關於在線匹配的研究提出了一個可廣泛應用於現今社會的新模型，如滴滴拼車、房東租客匹配等，成爲過去30年來有關問題的唯一突破性進展。研究獲國際計算機協會的ACM期刊刊登，是過去十年澳門地區發表於該期刊的第一篇文章。

澳大科技學院電腦及資訊科學系助理教授及智慧城市物聯網國家重點實驗室成員吳曉偉的論文《全面線上配對》（Fully Online Matching）發表在最新一期的ACM期刊。該期刊只登載那些對計算機科學有深遠影響的論文，過去十年總收錄文章不足400篇，其中15篇來自中國（包括港澳台）地區，是公認的理論計算機科學領域中最頂尖的期刊。

是次研究考慮了計算機圖靈獎獲得者Karp等人於1990年計算理論研討會發表的文章，是當中提出的二分圖在線匹配問題的一個擴展。吳曉偉將經典KVV模型拓展到任意（非二分）圖中並且允許所有點在綫出現，找出了能應用於現今社會、可產生廣泛應用的新模型，如滴滴拼車、房東租客匹配等不適用於KVV模型的場景；研究還提出了該問題的數個理論保障，成爲過去30年來關於Karp等人提出的任意圖在綫匹配問題的唯一突破性進展。

吳曉偉於2015年獲得香港大學計算機科學博士學位，及後於維也納大學擔任博士後研究員。他的研究方向主要是計算機科學理論、在線算法、近似算法、動態數據結構、城市大數據與智能技術等。