报告题目：Online bottleneck matching on a line

报告人：李伟东

报告时间：2022年7月7日9:30-12:00

报告地点：腾讯会议：854-659-459

邀请单位：88038威尼斯，离散数学及其应用省部共建教育部重点实验室

报告内容简介：

We study the online bottleneck matching problem on the line, which is to match a sequence of mrequests arriving one-by-one in an online fashion to a given set of m servers, such that each server is matched exactly once and the maximum distance between any request and its server is minimized. When the distances between any two adjacent servers are the same, we present an optimal online algorithms with a competitive ratio of m+1. When m=3, we present an optimal online algorithm whose competitive ratio is determined by the relative distance between adjacent servers and no more than 4.414, which matches the previous best lower bound proposed thirty years ago.

报告人简介：

李伟东，云南大学教授、博士生导师，主要从事离散优化、算法博弈论等领域的研究与教学。入选过中国科学院“西部之光”人才培养计划和云南省高层次人才培养支持计划“青年拔尖人才”专项，获云南省科学技术奖励1项。主持国家自然科学基金项目4项，担任中国运筹学会排序专业委员会常务理事、中国工业与应用数学学会图论组合及应用专业委员会委员、云南省高等学校数学类教学指导委员会秘书长。在Journal of Algorithms, Algorithmica, IEEE Transactions on Parallel and Distributed Systems, Journal of Parallel and Distributed Computing, Theoretical Computer Science, Journal of Combinatorial Optimization, Future Generation Computer Systems, 中国科学等国内外刊物发表学术论文。