设为首页 | 加入收藏 | 宁波大学
数学与统计学院
首页学院概况师资队伍科学研究人才培养党群工作学生工作中外合作办学校友之家招聘信息信息公开English
科学研究
 科研动态 
 科研成果 
 学术报告 
 科研机构 
 
当前位置: 首页>>科学研究>>学术报告>>正文
甬江数学讲坛240讲(2022年第24讲)
2022-05-13 13:41     (点击:)

报告题目(title):Approximation algorithms for multiprocessor scheduling with testing

报告人(Speaker):林国辉教授(加拿大阿尔伯塔大学)

报告时间(Time):202251713:00开始

报告地点(Venue):Join Zoom Meeting

https://ualberta-ca.zoom.us/j/99285115546?pwd=VXpFT3FFRUVPcGVDMEJtZnkvZ25Sdz09

Meeting ID:  992 8511 5546

Passcode: 491713

报告摘要(Abstract): Part II (Improved approximation algorithms for minimizing the total job completion time). For multiprocessor scheduling with testing to minimize the total job completion time, we present several first approximation algorithms with constant competitive ratios for various settings, including a $2 \varphi$-competitive algorithm for the non-preemptive general testing case and an expected $(0.0382 + 2.7925 (1 - \frac 1{2m}))$-competitive randomized algorithm, when $m \ge 37$ or otherwise expected $2.7925$-competitive, where $\varphi = (1 + \sqrt{5}) / 2 < 1.6181$ is the golden ratio and $m$ is the number of machines, a $(3.5 - \frac 3{2m})$-competitive algorithm allowing job preemption when $m \ge 3$ or otherwise $3$-competitive, and a $(\varphi + \frac {\varphi + 1}2 (1 - \frac 1m))$-competitive algorithm for the non-preemptive uniform testing case when $m \ge 5$ or otherwise $(\varphi + 1)$-competitive. Our results improve three previous best approximation algorithms for the single machine scheduling with testing problems, respectively.

报告人简介:Dr. Guohui Lin is currently a Professor of Computing Science at the University of Alberta, with tenure. He was an Assistant and then an Associate Professor at the same university since 2001. He obtained his PhD degree in Operations Research, specialized in Combinatorial Optimization, in 1998 from the Chinese Academy of Sciences (Thesis Supervisor Dr. Ding-Zhu Du); and he obtained Master of Science and Bachelor of Science in Applied Mathematics in 1995 and 1993, respectively, from the Zhejiang University. Dr. Lin has two lines of research interests, one is Combinatorial Optimization, mostly on approximability and inapproximability, and the other is Bioinformatics, especially on cattle genomics and human proteomics, metabolomics, and lipidomics.

 

关闭窗口
宁波大学 | 图书馆

地址:宁波市江北区风华路818号宁波大学包玉书9号楼;邮编:315211;电话:0574-87600795