NP And Approximation

• Know about the most famous classes of NP-complete problems, such as traveling salesman and the knapsack problem, and be able to recognize them when an interviewer asks you them in disguise.

• Know what NP-complete means.

• Computational Complexity - MIT 6.006 (video)

• Greedy Algs. II & Intro to NP Completeness - Simonson (video)

• NP Completeness II & Reductions - Simonson (video)

• NP Completeness III - Simonson (Video)

• NP Completeness IV - Simonson (video)

• Lecture 23 - NP-Completeness - CSE373 Skiena (video)

• Lecture 24 - Satisfiability - CSE373 Skiena (video)

• Lecture 25 - More NP-Completeness - CSE373 Skiena (video)

• Lecture 26 - NP-Completeness Challenge - CSE373 Skiena (video)

• Complexity: P, NP, NP-completeness, Reductions - MIT 6.046 (video)

• Complexity: Approximation Algorithms - MIT 6.046 (video)

• Complexity: Fixed-Parameter Algorithms - MIT 6.046 (video)

• Peter Norvig discusses near-optimal solutions to traveling salesman problem:

  • Jupyter Notebook

• Pages 1048 - 1140 in CLRS if you have it.

• Simonson: Approximation Algorithms - Youtube (video)