Home > Teaching > CS 655: Topics in Linear programming

CS 655: Topics in Linear programming

Course Number: CS655A (for PG), CS655B (for UG).
Units: 3-0-0-0-4 (CS655A, PG), 3-0-0-0-9 (CS655B, UG)
Pre-requisite: Basic linear algebra.
Course Contents:

The course will focus on basics of convexity theory, linear programming and application of linear programming in computer science. There will be broadly three parts of the course interrelated with each other.

 

The first part will cover the basics of convex sets, cones and polyhedras; essential to understand the structure behind convex optimization and motivate why so many special cases of it can be solved efficiently. This will also cover hyperplane separation theorems. Linear programming will be introduced and duality theory will be covered in detail.

 

The second part will talk about major algorithms which are used today to solve linear programming. The major three algorithms, simplex, ellipsoid and interior point method will be discussed. As an assignment they will have to convert a problem into a linear program and solve it using the existing linear programming solvers.

 

The final part will cover some applications in computer science. Specifically we will cover the multiplicative update method and a recent result where linear programming gives best approximation algorithm for a set of constraint satisfaction problems. Applications in network flows will also be covered.

 

Books and References:
  1. Linear algebra and its applications, Gilbert Strang.
  2. Convex optimization, Boyd and Vandenberghe.
  3. Linear programming, Dantzig and Thapa.
  4. Linear programming, Vasek Chvatal.