Uploaded April 2018 | Updated September 2026, 35 minutes ago
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html
Specific topics covered in this lecture: graph coloring applications, job scheduling, register allocation, non-approximability, solving large instances, SAT solvers, approximation schemes, provably-good heuristics, local vs global minima, "wishful thinking" approaches, minimum vertex covers, 2*OPT approximation for minimum vertex covers, worst-case vs. average-case behaviors, heuristic variations, counter-examples, bound-preserving meta-heuristics, maximum-cut problem, 2*OPT approximation for maximum cut, 2-OPT swaps and other variations, 2*OPT approximation for metric traveling salesperson tours, triangle inequality, (1+e)*OPT geometric TSP approximation
This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html
Specific topics covered in this lecture: graph coloring applications, job scheduling, register allocation, non-approximability, solving large instances, SAT solvers, approximation schemes, provably-good heuristics, local vs global minima, "wishful thinking" approaches, minimum vertex covers, 2*OPT approximation for minimum vertex covers, worst-case vs. average-case behaviors, heuristic variations, counter-examples, bound-preserving meta-heuristics, maximum-cut problem, 2*OPT approximation for maximum cut, 2-OPT swaps and other variations, 2*OPT approximation for metric traveling salesperson tours, triangle inequality, (1+e)*OPT geometric TSP approximation
