Premium Only Content

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
-
LIVE
Benny Johnson
2 hours agoBiden Appears With MASSIVE Scar on Face, New Health Horror Revealed! Sobbing Jimmy Kimmel FLEEING US
4,519 watching -
LIVE
The Big Mig™
4 hours agoBig Pharma's Puppets: RFK Jr. Takes on Congress
8,793 watching -
LIVE
Total Horse Channel
12 hours ago2025 Reno Snaffle Bit Futurity | Friday
18 watching -
26:40
Rethinking the Dollar
1 hour agoPeter Schiff: "Trump's Economy WORSE Than Biden" | Morning Check-In: Let's Talk...
3.95K11 -
1:55:15
Badlands Media
7 hours agoBadlands Daily: September 5, 2025
28.4K6 -
24:00
Bearing
4 hours agoThe Week LIBERALS Thought TRUMP DIED 💥 (And Went INSANE) 🤣
11.1K16 -
LIVE
GritsGG
2 hours agoWin Streaking!! 🫡!
36 watching -
1:41:36
Dear America
3 hours agoWelcome To The Dept Of WAR! RFK DESTROYS The CDC! + Should Trans Own Guns?!
81.3K53 -
2:57:08
Matt Kohrs
10 hours agoStocks Hit Record High, Breaking Jobs News || Live Day Trading & Analysis
20.8K -
Wendy Bell Radio
7 hours agoSchilling For Big Pharma
48.4K148