Course Objective

The objective of the course is to help students gain familiarity with fundamental combinatorial optimization techniques.

Course Contents

Introduction: Network Flows, Ford-Fulkerson Method, Edmonds-Karp Algorithm, Linear Programming (LP), LP Formulation for Flows, LP Duality, Weak Duality Theorem, Complementary Slackness, Farkas’ Lemma (10 lectures)

Linear Programming based Optimization: Minimum Spanning Trees, Shortest Paths, Totally Unimodular Matrices from Bipartite Graphs, Maximum Matching and Minimum Vertex Cover on Bipartite Graphs (10 lectures)

Polyhedral Techniques: Polyhedra and Polytopes of Linear Programs, The Matching and Perfect Matching Polytopes for General Graphs, The Independent Set Polytope, Polyhedral Characterization of Bipartite Graphs and Perfect Graphs (12 lectures)

Selected Advanced Topics like Semidefinite Programming based algorithms or Matroid based Algorithms (10 lectures)

Learning Outcomes:

  1. To familiarize with polyhedral combinatorics and linear programming techniques for designing efficient algorithms.
  2. To be able to design and analyze algorithms using the techniques taught in the course.

Text Books:

  1. Combinatorial Optimization: Polyhedra and Efficiency (Volumes A, B and C) by Alexander Schrijver. Springer-Verlag Berlin Heidelberg, 2003. ISBN: 978-3-540-44389-6.

References:

  1. Combinatorial Optimization by William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. John Wiley & Sons, 2011. ISBN: 9781118031391.
  2. Matching Theory by László Lovász, M. D. Plummer. American Mathematical Soc., 2009. ISBN 0821847597, 9780821847596.
  3. Geometric Algorithms and Combinatorial Optimization by Martin Grötschel, László Lovász and Alexander Schrijver. Springer-Verlag Berlin Heidelberg, 1993. ISBN: 978-3-642-78242- 8.

Metadata

Proposing Faculty: Department: Computer Science and Engineering Programme: MCaM Proposing date: Approved date: Proposal type: Offerings:

Past Offerings