Pi Day 2022 Talk - Limits of Approximability, Magic Numbers in Scheduling

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!

Slides: http://drpage.pagewizardgames.com/piday_2022_dpage_talk.pdf

Have a beautiful day!

Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
-Draikou
Patreon Supporters (Basic Support):
Patreon Supporters (Supporter Access!):
-Eric R
-----------------------------------------------------------
Become a supporter today! To support my work and mission to provide free or accessible Computer Science education (especially in theory), subscribe to the channel, share my videos. Please donate and contribute to support my work for more content:
PATREON: https://www.patreon.com/PageWizard
SUBSCRIBESTAR: https://www.subscribestar.com/drpage
PAYPAL: https://paypal.me/pagewizard

Follow also at:
FACEBOOK: https://www.facebook.com/DanielRPage
TWITTER: https://twitter.com/PageWizardGLE
QUORA: https://www.quora.com/profile/Daniel-R-Page
TWITCH: https://www.twitch.tv/pagewizard

#ComputerScience
#Algorithms
#TheoreticalCS