设为首页 | 加入收藏 | 宁波大学

 新闻中心
 学院新闻 通知通告 学术活动 学生工作 人才培养

 当前位置： 首页>>新闻中心>>学术活动>>正文
 甬江数学讲坛240讲（2022年第24讲） 2022-05-13 13:41     (点击：) 报告题目（title）：Approximation algorithms for multiprocessor scheduling with testing 报告人（Speaker）：林国辉教授（加拿大阿尔伯塔大学） 报告时间（Time）：2022年5月17日13: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