Keynote Speakers
Guohui Lin (University of Alberta)
Title: Approximation algorithms for multiprocessor scheduling with testing
Abstract: Scheduling with testing is a semi-online variant that has been recently studied. Mapping to various real-life applications where a preliminary action, operation or test can be executed before processing a job, in this talk, I will introduce the scheduling models and most existing approximation algorithms for two typical objective functions, makespan and the total job completion time. I will highlight the algorithm design ideas and the associated performance analysis techniques. Among several others, I will present an approximation algorithm for the min-sum objective --- the first 2\varphi-competitive algorithm for the non-preemptive multiprocessor scheduling with testing in the general testing case. This result also improves the previous best 4-competitive algorithm for the single machine.
Bio: 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.
Zhao Zhang (Zhejiang Normal University)
Title: On Approximating Partial Set Cover: Special Case and Extension
Abstract: Set Cover is a classic combinatorial optimization problem. In real applications, it is desirable to sacrifice coverage for economic benefit. This consideration leads to the partial cover problem, and there are a lot of new theoretical challenges arising from the partial cover requirement. In this talk, I'll introduce some of our recent progress in approximation algorithms in this field. In particular, I'll talk about a parallel algorithm for a special case of the problem (the minimum power partial cover problem) and a parallel algorithm for an extension of the problem (the minimum weight submodular cover problem).
Bio: Zhao Zhang is a professor of Zhejiang Normal University. She got doctor of Science degree from Xinjiang University in 2003. In 2008, she was selected into the New Century Outstanding Talents Support Program of the Ministry of Education, and in 2012, she was awarded the National Natural Science Outstanding Youth Fund. Currently, she is an outstanding professor of Zhejiang Normal University and a distinguished professor of Qianjiang Scholar of Zhejiang Province. Executive Director of Operations Research Society of China, Deputy Secretary general of Mathematical Planning Branch of Operations Research Society of China, member of Theoretical Computer Committee of China Computer Society. Editorial Board of Journal of Combinatorial Optimization and Journal of the Operations Research Society of China.