报告时间：2020年7月31日上午10:00开始
报告地点：ZOOM会议在线报告
会议链接：//zoom.us/j/96597702456
会议 ID: 965 9770 2456
密码: 685755
报告题目：Minimizing total job completion time in MapReduce scheduling
报 告 人：林国辉（加拿大阿尔伯塔大学 教授）
报告摘要：We follow up an earlier studied multiple-task parallel-machine scheduling model that captures the core challenges in MapReduce scheduling, with the optimization goal to minimize the total job completion time. The problem is a novel generalization of the classic two-stage flow-shop scheduling. We prove a new lower bound on the total job completion time, and based on which we present an O(n log n + N + m_1 + m_2)-time (9 - 3/m_1)-approximation algorithm, where n and N are the number of jobs and the total number of tasks, respectively, m_1 and m_2 are the numbers of map and reduce machines, respectively, and they can even be part of the input. Our algorithm improves the previous best 12-approximation, and it reduces to the best approximation algorithms for several interesting or well studied special cases. We confirm through numerical experiments on 828,100 instances that both our lower bound and our algorithm significantly outperform, and the empirical mean approximation ratio is only 1.7582 with standard deviation 0.2584.
报告人简要：林国辉教授现在加拿大阿尔伯塔大学任教，主要研究组合优化及生物信息学，在网络优化及DNA序列分析等问题上做出了一系列具有国际影响力的工作，主要结果发表在SIAM Journal on Computing, Algorithmica, JCSS, JOS, EJOR,TCS等国际重要期刊。
