||C.Papadimitriou and K. Steiglitz, Combinatiorial Optimization, Prentice-Hall India, 1996
Gibert Strang, Linear Algebra and its Applications, Harcourt Brace Jovanovitch, 1988
V. Chvatal, Linear Programming and Applications, 1982.
||Vector Spaces: bases, echelon forms, rank and determinants. Gauss elimination and its complexity, Inner products, Gram- Schmidt orthogonalization. Linear transformations.
Optimization: Modeling and formulation of optimization problems. Linear costs and convex domains. Mean-square (distance) minimizations. Linear programming and the Simplex algorithm. Duality and the primal dual method. Examples from combinatorial optimization. Shortest paths, network flows and matchings. Approximation and randomized algorithms. Matrix Games.