Prof. Xiaowei Wu has joined the University of Macau since March, 2020. He is an assistant professor of the Department of Computer and Information Science, and the research member of the State Key Laboratory of Smart City Internet of Things. After joining the UM, Prof. Wu’s article “Fully online matching” was published in the latest issue of the Journal of ACM (JACM), 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, Journal of ACM has published less than 400 articles, of which only 15 come from China (including Hong Kong, Macao, and Taiwan). It is also the first paper from Macao that has been published in this journal in the past decade.

The path to a computer science scholar

FST invited Prof. Wu to conduct an interview to share his academic research and personal experience. Prof. Wu graduated from the University of Science and Technology of China with a bachelor degree in Computer Science. It is a national key university directly managed by the Chinese Academy of Sciences. The quality of undergraduates of the University of Science and Technology of China has always been among the best in China. In this four-years programme, Prof. Wu started to understand the approximation algorithm, and gradually developed an interest in computer science theory. In 2011, he successfully won the excellent graduate award. Prof. Wu shares with us, “The undergraduate programme is meaningful for me as it has established a solid theoretical foundation, and lead me to the path of a computer science scholar.” To complete his P.hD. degree, Prof. Wu chose the University of Hong Kong. The 1st year in HKU, Prof. Wu shared that he could not find his own research goals until he met his enlightening teacher – Dr Chan, Hubert T.H., another scholar of approximate algorithms, Before joining UM, Prof. Wu also went to Europe worked as a postdoctoral fellow at the University of Vienna in 2019 for achieving more oversea experiences.

Fully Online Matching

In regards of the features of his paper “Fully Online Matching”, Prof. Wu explains to us by using Didi carpool service, “Since the requests of carpooling order are real-time, and has no data can be predicted. Therefore, to accurately match several people with vehicles, it is necessary to rely on fully online matching.” Prof. Wu shared that 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-bipartite) graph and allowing all points to appear online. Prof. Wu says, “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 graph ​online matching problems proposed by Karp et al in the past 30 years.

Conducting research and teaching at UM

When asking about his feeling of successfully published an article in the Journal of ACM, Prof Wu says, “I am lucky that my research has caught up with the trend of artificial intelligence and big data.”  For students who are also eager to pursue a research career, Prof. Wu suggested that interest and enthusiasm are the most important components, followed by the solid theoretical basis for future research. The reason that he chose UM is because he believes that UM has great potential. It is located in the Greater Bay Area and has many state key laboratories and research centres. The rapid growth of UM in recent years have great significance to both Macao community and the Greater Bay Area. Prof. Wu is looking forward to the teaching in the near future. He hopes to bring more comprehensive theoretical knowledge of computer science to students and cultivate more talents for the local community and the Greater Bay Area.

吳曉偉教授於今年3月正式加入澳大,成為科技學院電腦及資訊科學系助理教授及智慧城市物聯網國家重點實驗室成員。而就在加盟澳大2個月後,吳曉偉教授的論文《全面線上配對》獲發表在最新一期的ACM期刊上 (Journal of ACM)。由於ACM期刊被公認是理論計算機科學領域最頂尖的期刊,此期刊只登載那些對計算機科學有深遠影響的論文,所以能在ACM期刊發表論文是不少理論計算機科學學者的夢想。此期刊過去十年總收錄文章不足400篇,其中僅有15篇來自中國(包括港澳台)地區。吳教授的論文也是過去十年澳門地區發表於該期刊的第一篇文章。


科技學院本次有機會採訪吳教授,並邀請他分享他個人學術研究及經歷。吳教授本科畢業於中國科學技術大學,這是由中國科學院直屬管理的全國重點大學,本科生質量一直在全國高校中名列前茅。四年間,吳教授由開始了解近似算法,直到後來慢慢培養出對計算機科學理論的興趣,2011年更獲得優秀畢業生獎。吳教授直言本科為他建立了堅實的理論基礎,奠定了往後的研究之路。2011年本科畢業後,吳教授前往香港大學修讀博士學位,剛開始時還在尋覓自己的研究方向,後來他遇上他的啟蒙老師 — 陳子康教授,另一位近似算法的學者,慢慢開始建立起自己的研究目標。加入澳大前為了增廣見聞,吳教授於2019年更遠赴歐洲並在維也納大學擔任博士後研究員。


談及本次論文的特色,吳教授採用滴滴拼車做例子,由於拼車的下單請求是實時,且沒有未來數據可以預測,要把多個人和車輛準確配對,就要依賴完全在線配對。吳教授表示《全面線上配對》考慮了計算機圖靈獎獲得者Karp等人於1990年計算理論研討會發表的文章,當中提出的二分圖在線匹配問題的一個擴展。這次文章將經典KVV模型拓展到任意(非二分)圖中並且允許所有點在綫出現,這解決了完全在線配對等科學難題。吳教授說: 「這次我們把原來的經典模型擴展到更普遍的模型,可廣泛應用於目前社會需求,如房東租客匹配﹅滴滴拼車等KVV模型不適用的場景。」論文還提供了該問題的數個理論保障,成爲過去30年來關於Karp等人提出的任意圖在綫匹配問題的唯一突破性進展。



吳曉偉教授 – 科技學院電腦及資訊科學系
Prof. Xiaowei Wu – Assistant professor
of CIS and research member of IOTSC

Prof. Xiaowei Wu’s research has been
accepted by the Journal of ACM