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
StoneMountain64
5 hours agoBattlefield 6 News and Extraction Gaming
137 watching -
9:21
Tundra Tactical
1 hour agoThe Dumbest Gun Questions Of All Time Answered! Part 2
541 -
LIVE
LumpyPotatoX2
36 minutes agoWorld of Tanks 2.0 | Public Service Announcement - #RumbleGaming
26 watching -
LIVE
GritsGG
4 hours agoQuad Win Streaks w/ Bobby Poff!🫡 Most Wins in WORLD! 3600+
72 watching -
LIVE
Badlands Media
11 hours agoQuite Frankly Ep. 23
301 watching -
1:31:41
Redacted News
3 hours agoNew Charlie Kirk Video Evidence Could Change EVERYTHING | Redacted w Natali & Clayton Morris
165K188 -
22:10
Jasmin Laine
3 hours ago"You Promised Them $1BILLION!?"—Liberal Gets LAUGHED Out of Parliament
7.49K13 -
1:54:22
vivafrei
5 hours agoOstrich Farm UPDATE! And Live with Tyler Fischer Talking REAL Cancel Culture He is Experiencing!
167K34 -
31:39
Michael Franzese
3 hours agoAmerica’s Human Trafficking Crisis EXPOSED by Former Mobster
29.1K14 -
LIVE
Wayne Allyn Root | WAR Zone
7 hours agoWatch LIVE: The War Zone Podcast with Wayne Allyn Root
53 watching