Theory of Computation CS6160 Lecture 12 part 2 of 2 Gabriel Robins Spring 2018 Apr 17 @GabrielRobins
Theory of Computation CS6160 Lecture 12 part 2 of 2 Gabriel Robins Spring 2018 Apr 17  @GabrielRobins
Uploaded April 2018 | Updated November 2026, 5 days ago
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS6160 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs6160/ and other related videos at http://www.cs.virginia.edu/robins/videos.html

Specific topics covered in this lecture: NP-completeness of planar graph 3-colorability, "gadget"-based proof, 3-colorability constraint propagation, NP-completeness of max-degree-4 planar graph 3 colorability, combining parameter constraints, composing reductions, four-color theorem, computer-generated proofs, planarity testing in linear time, colorability on torus-embedable graphs, coloring theorems for other manifolds, applications of graph coloring, optimization and local minima, heuristics and approximations, "wishful thinking" algorithms, 2*OPT vertex cover heuristic, practical optimizations, meta-heuristics, some NP-complete problems are not approximable, approximation-preserving transformations, 2*OPT approximation heuristic for maximum cuts, trying to avoid getting trapped in local minima, preview of provably-good TSP heuristics, approximating proofs and zero-knowledge protocols
Theory of Computation CS6160 Lecture 12 part 2 of 2 Gabriel Robins Spring 2018 Apr 17Algorithms Lecture 12, Oct 3, 2019Berenika and Gabe dancingAlgorithms Lecture 04, Sept 5, 2019 - PanoptoAlgorithms Lecture 03, Sept 3, 2019Theory of Computation (CS3102), Lecture 16, Professor Gabriel Robins, Spring 2018Gabe and Meghan dancing - Dernière DanseDance Party, River, Jen & Zach, Lydia & Tim, Natalya & Mike, May 2025Algorithms Lecture 10, Sept 26, 2019Tim and Gabe dancing, with 20 spins in a row! (Marriott Hotel, March 2026)Theory of Computation (CS3102), Lecture 22, Professor Gabriel Robins, Spring 2018Theory of Computation (CS3102), Lecture 21, Professor Gabriel Robins, Spring 2018 Panopto
Gabriel Robins |

Theory of Computation CS6160 Lecture 12 part 2 of 2 Gabriel Robins Spring 2018 Apr 17

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER