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:
- To familiarize with polyhedral combinatorics and linear programming techniques for designing efficient algorithms.
- To be able to design and analyze algorithms using the techniques taught in the course.
Text Books:
- 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:
- Combinatorial Optimization by William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver. John Wiley & Sons, 2011. ISBN: 9781118031391.
- Matching Theory by László Lovász, M. D. Plummer. American Mathematical Soc., 2009. ISBN 0821847597, 9780821847596.
- 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 |