主讲：张乾坤，华中科技大学网络空间安全学院，副研究员

时间：2024年12月5日14:00

地点：同济大厦A楼306教室

讲座摘要:

在线匹配问题是在线算法研究领域的核心模型，它涉及在输入逐渐给出时做出即时决策的问题。这类问题在现实生活中应用广泛，比如在线广告投放、任务分配等。在线匹配问题的关键挑战在于如何在不完全信息的情况下做出优秀的决策。在线匹配问题的传统模型主要关注二分图中的单侧在线模式，即一部分顶点是离线的（已知的），而另一部分顶点是在线的（逐步到达的）。在线匹配问题中的“随机奖励”模型是一种将边与成功概率相关联的泛化模型，它捕捉了在线广告中的按点击付费模式。在这种模型中，每个匹配的边都有一个与之关联的成功概率，这个概率可以看作是奖励的随机性。这种随机性增加了算法设计的复杂性，因为算法需要在不确定性下做出决策。本问题自2012年在FOCS大会提出后最优的算法至今悬而未决。本报告将介绍报告人在该模型上的一系列突破和研究进展。

演讲嘉宾简介:

张乾坤，博士，现任华中科技大学网络空间安全学院副研究员，硕士生、博士生导师。2017年于浙江大学竺可桢学院计算机科学与技术系获工学学士学位，2021年于香港大学计算机科学系获哲学博士学位，并荣获香港大学研究生奖学金（UPF）和工学院奖学金。研究领域包括：（1）理论计算机科学，致力于设计具有可证明的性能保证的在线算法或近似算法；（2）可信人工智能，致力于研究主流人工智能模型、技术的可解释性、公平性和安全性等。相关工作发表在国际顶级会议STOC、FOCS、CCS、WINE、ICML、INFOCOM和期刊SICOMP、TNSM等。主持国家自然科学基金青年项目、湖北省自然科学基青年项目、网络空间安全教育部重点实验室开放课题重点项目、CCF-华为胡杨林理论计算机科学专项、CCF-滴滴盖亚学者等项目，获评武汉英才、东湖青年学者等称号。