跳过导航

澳大学者研究在线匹配有突破性进展 获国际顶尖ACM期刊刊登

吴晓伟

澳门大学学者一项关于在线匹配的研究提出了一个可广泛应用于现今社会的新模型,如滴滴拼车、房东租客匹配等,成为过去30年来有关问题的唯一突破性进展。研究获国际计算机协会的ACM期刊刊登,是过去十年澳门地区发表于该期刊的第一篇文章。

澳大科技学院电脑及资讯科学系助理教授及智慧城市物联网国家重点实验室成员吴晓伟的论文《全面线上配对》(Fully Online Matching)发表在最新一期的ACM期刊。该期刊只登载那些对计算机科学有深远影响的论文,过去十年总收录文章不足400篇,其中15篇来自中国(包括港澳台)地区,是公认的理论计算机科学领域中最顶尖的期刊。

是次研究考虑了计算机图灵奖获得者Karp等人于1990年计算理论研讨会发表的文章,是当中提出的二分图在线匹配问题的一个扩展。吴晓伟将经典KVV模型拓展到任意(非二分)图中并且允许所有点在线出现,找出了能应用于现今社会、可产生广泛应用的新模型,如滴滴拼车、房东租客匹配等不适用于KVV模型的场景;研究还提出了该问题的数个理论保障,成为过去30年来关于Karp等人提出的任意图在线匹配问题的唯一突破性进展。

吴晓伟于2015年获得香港大学计算机科学博士学位,及后于维也纳大学担任博士后研究员。他的研究方向主要是计算机科学理论、在线算法、近似算法、动态数据结构、城市大数据与智能技术等。

查看图库