CS 698J/R: Topics in Linear programming

Course description:

Linear Programming is a special class of mathematical optimization where the constraints and the cost function are linear. This class of problems have known efficient algorithms and wide applications in various fields.
The course will have detailed introduction to the field of linear optimization. The first part of the course will cover the basics of convex optimization and look at various aspects of linear programming which make it more tractable. Various known algorithms to solve linear programs will also be covered. In the later half, the focus will be on the applications of linear programming in theoretical computer science.

CS 698J/R: Notes

Course notes:

Date Topic Link
31st July 2014 Introduction to mathematical optimization Lecture 1
1st August 2014 Linear algebra Lecture 2
7th August 2014 Linear combinations Lecture 3
8th August 2014 Convex sets Lecture 4
14th August 2014 Properties of convex sets Lecture 5
16th August 2014 Linear programs Lecture 6
21st August 2014 Simplex method: The idea Lecture 7
22nd August 2014 Simplex method Lecture 8
28th August 2014 Hyperplane separation theorems Lecture 9
29th August 2014 Duality Lecture 10
4th Sept 2014 Strong duality Lecture 11
5th Sept 2014 Revision
11th Sept 2014 Revision
12th Sept 2014 Quiz Lecture 14
25th Sept 2014 Max flow and min cut Lecture 15
26th Sept 2014 Primal dual method Lecture 16
9th October 2014 Interior point methods Lecture 17
16th October 2014 Guest lecture: Sreyash Kenkre Lecture 18
17th October 2014 Guest lecture: Sreyash Kenkre Lecture 19
18th October 2014 Quiz 3 Lecture 20
19th October 2014 Guest lecture: Rishabh Vaid Article , Video
25th October 2014 Multiplicative weight update method Lecture 23
26th October 2014 LP-based algorithm for vertex cover Lecture 24

CS 698C/K: References


Linear Algebra

Functional Analysis

Interior point method

Project: Multiplicative weight update method

Constraint satisfaction problems