Advanced Algorithms (Fall 2014)

Shay Mozes

Lecture 9 Video [previous] [next]

[+] Integer Linear programming, LP duality and a bit of Randomized algorithms

We discuss approximation algorithms for linear integer programs that use optimal solutions to the relaxation LP problem. We then introduce LP duality, show that the max-flow min-cut theorem can be obtained using LP duality, and show an approximation algorithm based on the concept of complementary slackness. In the last few minutes we start discussing randomized algorithms.

Download Video: 720p

Lecture notes, page 1/37 • [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.