甬江数学讲坛88讲(2020年第15讲)-首页 - 伟德存9送54网址

学术活动

伟德存9送54网址——伟德外围投注app

发布日期:2020-07-23 作者:数学与统计学院 文章来源:未知  责任编辑:

报告时间: 2020731日上午10:00开始

报告地点:ZOOM会议在线报告

会议链接:http://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等国际重要期刊。

下一条:中法联合学院联合大讲堂“谈天说地”系列讲座第20讲

关闭

Baidu
sogou