MATHEMATICAL PROGRAMMING (CS 450)

The course will cover the following topics (changes will be made depending on the progress of the class).

(1)

Linear Programming: (i) Geometry of Polytopes and the Simplex Method.

(ii) Khachiyan's ellipsoidal method

(iii) Interior Point methods- Karmarkar's method and beyond.

(iv) Linear time LP algorithm for fixed dimensions.

(2)

Duality theory and its applications to

(i) Matching.

(ii) Min-cost flows.

(iii) Muti-commodity flows

(3)

Quadratic Programming

(4)

Semi-definite Progamming

Besides the regular examinations, students will be required to spend substantial time on a project. Both theoretical and experimental work will be encouraged.

IMPORTANCE of the course The course will concentrate on new efficient methods for solving linear and non-linear programming problems. Linear and Non-Linear programming are becomming increasingly important in solving problems optimally and for approximations.

Pre-requisites: Introductory data Structures and algorithms, Linear algebra, Combinatorics. Contact me for more information.


Sanjiv Kapoor