Pi Day 2022 - Invited Talk!
https://youtu.be/2O1b6UBqDgQ

In the study of algorithms, we desire provably-correct algorithms that efficiently solve problems.  In this talk, the area of approximation algorithms is introduced in the context of determining the existence of efficient algorithms for hard optimization problems.  If P is not equal to NP, which is one possibility for the outstanding and fundamental P vs. NP problem, then for some intractable problems there may only exist polynomial-time algorithms that can compute approximately close answers to optimal solutions, but no better than multiplicatively by some “magic number”.  The talk will briefly introduce a mixture of algorithms, computational complexity theory, and recent developments focusing on intractable problems intersecting scheduling and graph theory.  


On March 14, 2022 I delivered this talk for University of Regina's Pi Day Event (with the Dept. of Math & Stats), organized by the Mathematics, Actuarial Science, and Statistics Student Society (MASS).  I am very thankful for their invitation to give this talk!  Thank you for the time to talk about Algorithms!  


Remark:  I did not mention it properly given the time constraints, but Svensson in 2010 proved P|prec|Cmax has no 2-\epsilon approximation algorithm, relying on assumptions of a variant of the Unique Games Conjecture.  So if you believe that variant is true, then List Scheduling is optimal with respect to the approximation ratio!  


Have a beautiful day!