Combinatorial Optimization I

Brief Overview of Linear and Nonlinear Programming, Kuhn-Fourier Elimination Scheme, Farkas Lemma, Constrained Optimization through Lagrange multipliers for equation and inequality based systems, Karush-Kuhn-Tucker Theorem, Strong Duality Theorem of Linear Programming. Network Flows. Max-flow Mincut Theorem, Algorithms for maximizing flows, min cost flow Problem and its electrical equivalent, Menger`s Theorems. Graph Optimization Problems. Maximum spanning tree, matching and covering, shortest path problem, graph colouring problems. Introduction to Matroids. Axioms for matroids, The greedy algorithm and the related characterization of matroids. Submodular functions as a unifier and as a powerful tool for applied problems. Principal Partition and Principal Lattice of Partitions of submodular functions.