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: heuristics and approximation algorithms, 2*OPT traveling salesperson heuristic, triangle inequality, 1.5*OPT TSP heuristic, minimum matchings, handshaking lemma, Euler tours, non-uniqueness of minimum spanning trees, negative weights, repeat node visits, bound-preserving post-processing, 2-OPT / 3-OPT / k-OPT, meta-heuristics, bounds vs. solution quality in practice, sorting example, bounds don't survice transformations, approximability and non-approximability, solving large SAT instances, branch-and-bound, Arora' s TSP approximation scheme, graph isomorphisim, friend-or-foe identification, zero-knowledge proofs, exams as "proof protocols", zero-knowledge proofs for other NP problems, IP=PSPACE, zero-knowledge protocols in financial transactions
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: heuristics and approximation algorithms, 2*OPT traveling salesperson heuristic, triangle inequality, 1.5*OPT TSP heuristic, minimum matchings, handshaking lemma, Euler tours, non-uniqueness of minimum spanning trees, negative weights, repeat node visits, bound-preserving post-processing, 2-OPT / 3-OPT / k-OPT, meta-heuristics, bounds vs. solution quality in practice, sorting example, bounds don't survice transformations, approximability and non-approximability, solving large SAT instances, branch-and-bound, Arora' s TSP approximation scheme, graph isomorphisim, friend-or-foe identification, zero-knowledge proofs, exams as "proof protocols", zero-knowledge proofs for other NP problems, IP=PSPACE, zero-knowledge protocols in financial transactions










