Approximation Algorithms for Makespan Minimization on Unrelated Parallel Machines
Thursday, July 22, 1-2 p.m.
Dr. Daniel Page
In this talk, a brief introduction to approximation algorithms
in relation to unrelated parallel machine scheduling is provided. The talk consists of two parts: (1) For the past 30 years, despite intensive research, it continues to remain unknown whether there exists an approximation algorithm with constant approximation ratio less than 2 for this problem. Highlighted in this talk is a summary of recent developments by the speaker to discover new approximation algorithms for interesting special cases of the problem, such as the graph balancing problem, that have approximation ratios less than 2. (2) In addition, the speaker discusses new results and open problems for a generalization of the problem where a basic modelling of fault tolerant scheduling is introduced called scheduling with bag constraints.
Presented by Department of Computer Science