The Remarkable BEST-SAT Algorithm

A dive into the remarkable BEST-SAT approximation algorithm. Created as a part of SoME2:    • Summer of Math Exposition 2 Invitation   ------------------ Timetable: 0:00 - Introduction 2:21 - RAND-SAT 3:35 - LP-SAT 8:49 - BEST-SAT 10:11 - Outro ------------------ Source code: https://github.com/xiaoxiae/videos/tr... Music: Thannoid by Blue Dot Sessions: https://app.sessions.blue/browse/trac... Software used: Manim (animation software): https://github.com/ManimCommunity/manim/ Kdenlive (video cutting): https://kdenlive.org/en/ ffmpeg (audio/video processing): https://ffmpeg.org/ OBS (audio/video recording): https://obsproject.com/download arecord (audio recording): https://linux.die.net/man/1/arecord sox (audio processing): http://sox.sourceforge.net/ Vector Magic (image vectorization): https://vectormagic.com/ Inkscape (vector image editing): https://inkscape.org/ Social media: Website (for other things I'm up to): https://slama.dev/ ► Patreon (if you'd like to support me):   / ytoms   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 https://slama.dev/lecture-notes/best-...