题目: 秘书问题与在线算法
时间:2015年1月5日上午9：00
地点:东五楼210
讲座摘要：
秘书问题是上个世纪六十年代提出的一个经典的在线问题。在这个问题中，雇主计划从n个完全随机到来的候选人中选择J个秘书，在线体现在候选人一个接一个到来，每面试完一个候选人，面试官才知道当前候选人的信息，并且要立即决定是否录取这个人，不可反悔。我们研究了这一问题的并行推广，提出了一种基于观察-选择的确定性并行算法。这个算法具有高效、易实现的特点，而且利用互补松弛定理等可以证明该算法是最优的。在这一讲座中还将介绍我们在在线匹配问题上的一些研究工作。
孙晓明 简介：
孙晓明，中科院计算所研究员。05年毕业于清华大学，获博士学位。曾任清华大学高等研究院助理研究员、副研究员。主要研究方向为算法与计算复杂性。入选中组部万人计划（青年拔尖人才），获基金委首批优秀青年基金资助，曾获中国密码学会优秀青年奖。目前担任JCST、《软件学报》、《计算机研究与发展》等杂志编委。
