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.

Past Offerings

  • Offered in Aug-Dec, 2022 by Krithika R

Course Metadata

Item Details
Course Title Combinatorial Optimization
Course Code CS6002
Course Credits 3-0-0-3
Course Category PME
Proposing Faculty Jasine Babu & Krithika Ramaswamy
Approved on Senate 11 of IIT Palakkad
Course prerequisites Basic knowledge of Linear Algebra & Algorithms
Course status NEW