Advanced Algorithms (Fall 2014)

Shay Mozes

Lecture 4 Video [previous] [next]

[+] Approximation Algorithms

In this lecture we continue our discussion of approximation algorithms. We present algorithms for Euclidean TSP and Bin-Packing, and a polynomial-time approximation scheme (PTAS) for Knapsack. We also briefly discuss the PCP theorem and hardness of approximations.

Download Video: 720p

Lecture notes, page 1/49 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email me.