Go to page content

Approximation Algorithms for Makespan Minimization on Unrelated Parallel Machines

Thursday, July 22, 1-2 p.m.

Online

Dr. Daniel Page

Faculty Candidate

Abstract:

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.

Join: https://mun.webex.com/mun/j.php?MTID=m605c703412b51b43bce0d798ecbde9ab

Presented by Department of Computer Science

Event Listing 2021-07-22 13:00:00 2021-07-22 14:00:00 America/St_Johns Approximation Algorithms for Makespan Minimization on Unrelated Parallel Machines Dr. Daniel Page Faculty Candidate Abstract: 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. Join: https://mun.webex.com/mun/j.php?MTID=m605c703412b51b43bce0d798ecbde9ab Online Department of Computer Science