IntroductiontoOnlineAlgorithm
信管·讲座回顾
讲座时间
-04-：00
主讲人
唐志皓老师
4月27日晚六点，主题为IntroductiontoOnlineAlgorithm的讲座在国定路梯三举行，本次讲座有幸邀请到了唐志皓老师为同学们做在线算法相关知识的介绍。唐志皓老师是上海财经大学ITCS助理教授，曾获香港大学PhD博士学位，北京大学数学、经济学双学士学位。主要研究兴趣为在线算法、算法博弈论、谱图理论等。唐老师用大量的实例与严谨的证明向同学们展示了在线算法的原理及其的应用，讲座内容科学严谨，同学们反响热烈。
在线算法（OnlineAlgorithm）与离线算法（OfflineAlgorithm）有什么差异？这是老师给同学们提出的第一个问题。老师解释，离线算法其实指的是在给定输入和求解目标的情况下设计出的能得到求解目标的算法，而在线算法的在线是指输入会一部分一部分的给定。算法必须在不知道所有输入的情况下处理问题的部分来输入实现问题的输出。在线算法往往并不能求出最优解，但可以让求得的解与最优解相靠近。在介绍的同时老师用雪橇租赁这一经典案例形象地向同学们展示了在线算法应用的实际情况，同时用数据言简意赅地解释了竞争比的概念。
随后老师介绍了一些经典的在线算法问题。首先例举了Thek-serverProblem，在观察该问题后可以发现贪心算法并不能得出最优解，反而可能会造成成本在特定情况下趋向无穷大，因而贪心算法被抛弃。人们在对该问题的深入研究中发现，最优的确定性算法得出的期望远比采用最优随机性算法得出的大，因而采用随机算法可以得到更优的结果。接下来的两个案例SecretaryProblem与ProphetInequality相类似，唐老师通过对问题与算法的介绍向同学们揭示在线算法的奇妙，加固了同学们对在线算法的认知。
在这么多的案例中，老师认为自己最熟悉的还是OnlineMatching(又称为在线二分组匹配)。老师例举了一个经典模型，假设有两排圆点，一排圆点固定，另一排圆点依次在线到达，每一个到达的圆点都有若干可以与其匹配的固定点，选择一个尚未被匹配过的固定点与其匹配,预期实现的目标是实现最多的匹配。在确定性算法中，贪心算法最优，但是人们还会想到能否用随机算法匹配，在这样的想法的支持下，人们发现了Ranking算法，找到了最优的解答。在线二分组匹配在现实中也有很多的应用，网络上广告位的拍卖使用的就是Ranking算法来实现利益的最大化。
在讲座的最后，老师回顾了整场讲座内容，并总结说，在这种在线的问题中，尽管随机性算法的设计与分析会比确定性的算法复杂很多，但往往随机性算法要比确定性算法得出的结果更优，因而在日常生活遇到类似的问题时，随机性算法往往都是不可避免的。
文案
王若阳
图片
学术部
编辑
FX
预览时标签不可点收录于话题#个上一篇下一篇