Advanced Algorithms (Fall 2014)

Shay Mozes

Lecture 8 Video [previous] [next]

[+] Linear programming

We first discuss poblem set 2. Then we return to linear programming and present the simplex algorithm. After a couple of examples we introduce the integer linear programs (ILP), which are NP-hard problems. We discuss solving ILPs using the branch and bound heuristic, and introduce the concept of an LP relaxation of an ILP.

Download Video: 720p

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