报告题目（title）：Approximation algorithms for multiprocessor scheduling with testing
报告人（Speaker）：林国辉教授（加拿大阿尔伯塔大学）
报告时间（Time）：2022年5月17日13:00开始
报告地点（Venue）：Join Zoom Meeting
//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.
