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