The Remarkable BEST-SAT Algorithm

A dive into the remarkable BEST-SAT approximation algorithm.

------------------

Timetable:
0:00 - Introduction
2:21 - RAND-SAT
3:35 - LP-SAT
8:49 - BEST-SAT
10:11 - Outro

------------------

Source code:

Music:

Software used:

Social media:

Thanks to Matěj Kripner for proofreading the script and reviewing the early drafts of the video!

------------------

[EN] Notes from Jiří Sgall's Approximation Algorithms lecture

[tomtheultimatepro]

Great video! I got a little confused at the LP-SAT proof part when you were talking about Jensen's inequality and concave functions. I'm pretty sure the function shown at 7:17 is a convex function. I think the inequality is the other way around, i.e. f(x) >= a + bx if f concave on [0, 1]. Only then can you substitute the bound at 8:10.

[cubostar]

As a computer science and mathematics major, this content really hits the niche intersection I'm interested in. Thank you for this high-level content that you've somehow made easier than expected to digest.

[AssemblyWizard]

Fun fact: if every clause uses exactly 3 distinct variables, RAND-SAT gives us 7/8 of the optimum in expectation (actually 7/8 of all clauses), but approximating this case to anything higher than 7/8 of the optimum is NP-complete

[khoda]

Yes, another underrated youtube channel. We love those youtube :)

[xdman]

what does it mean to choose one or the other algorithm for each clause independently? The algorightms work on whole expression, and the clauses share variables. I am confused. Also, not easy to find references of BEST SAT online

[dfparker]

Suggestion: boost your volume. It is wildly lower than other yt vids

[IsraelJacobowich]

Can't we just model the factories problem with a bipartite graph and solve for max-match in linear time ?

[blacklistnr]

If you breathed for like 5 seconds at the start to leave me enough time to turn the volume up without missing half the premise of the full video it would be great :)))

[MrNathansikora]

I didn't understand what it means to average LP SAT with random SAT, how is BEST sat defined?

[frankargenti]

i truly cannot understand a thing rise the volume

[RonWolfHowl]

I don't understand why RAND-SAT gets better as the number of variables increases…