CS 655: Topics in Linear Programming

Announcements

Course Notes

Topic Link
Introduction to linear programming, basics of linear algebra, definitions. Introduction
Convex sets, properties, simplex method and degeneracy Convexity
Separating hyperplanes, duality theory, strong duality Duality
Applications of strong duality, Algorithmic game theory, Communication complexity Minimax
Maximum flow, minimum cut and primal dual approach Primal dual method
Relaxation and approximation algorithm for set cover Set cover
Semidefinite matrices and programs, Goemans-Williamson algorithm Semidefinite programs (SDP)
Representation of Boolean functions, approximate degree Boolean functions

Administrative details:

Course description:

Linear programming is a special class of mathematical optimization problems where the constraints as well as the cost function is linear. This class of problems have known efficient algorithms, deep structural properties and wide applications in various fields. The course will provide detailed introduction to the field of linear optimization.

We will start by covering the basics of convex optimization and linear algebra briefly. The background material will not be covered in detail; it is expected that either students know it or can read and recall it. We will move to the definition of linear programs next and show how to model various problems as a linear program. The last part of the first half will give outline of some approaches to solve a linear program.

The later part of the course will focus on applying linear programming in theoretical computer science. We will cover many interesting applications in diverse fields such as network algorithms, complexity theory and approximation theory. If time permits, a small introduction to semidefinite programming will be given with a basic application.

References

Optimization

Linear Algebra