Home Research Teaching Publications index

**January 2020**

This course will give an introduction to combinatorial optimization. This is an elective course for both undergraduate and postgraduate students.

- LT3, Thu 9.30-11.00 am
- LT3, Fri 9.30-11.00 am

Algorithms and Linear algebra course.

- Combinatorial optimization by Papadimitriou
- Linear programming by Matousek

- Prof. Sundar Vishwanathan's notes
- Theory of Linear and Integer programming by Schrijver
- Linear programming by Gass
- Approximation algorithm by Vazirani
- Algorithm design by Tardos

- Introduction to combinatorial optimization - Some example problems.
- Linear Programming (LP)
- The problem and its variants
- Reductions to LP - solving other problems by reductions to LP
- Properties of LP
- Algorithms for solving LP
- Simplex
- Polynomial algorithm(s)

- Introduction to Integer programming (if time permits)
- Introduction to Convex optimization (if time permits)

- Midterm (25%) — Final (40%) - Assignments(25%) - Term paper(10%)

We expect every student to follow the highest standards of integrity and academic honesty. Copying/sharing code in exams, homeworks, labs are not allowed. See the IIT Goa policy for academic malpractices.

# | Date | Topic | Resources |
---|---|---|---|

1 | 8/1 | Introduction to combinatorial optimization. Matrix multiplication | |

2 | 9/1 | Knapsack problem | Tardos, Prof. Ranade's lecture |

Bipartite matching problem | Prof. Ranade's lecture | ||

3 | 16/1 | Bipartite matching problem continued. | " |

Introduction to Linear algebra - Vectors, matrices, row view, column view, matrix multiplication, special matrices: square, symmetric, identity. Inverse of a matrix | any linear algebra book | ||

4 | 17/1 | Row/Column space, rank, orthogonal vectors, null space, fundamental theorem of linear algebra | any linear algebra book |

5 | 21/1 | Linear algebra tutorial - geometry of lines, gaussian elimination, when is Ax=b solvable?, "special" solutions when Ax=b has infinite solutions. | |

6 | 23/1 | Introduction to Linear programming - diet problem example, the LP problem, 2-D geometric view and finding min and max | |

7 | 24/1 | Different LP problems. Feasible solution, basic feasible solution (bfs) | |

8 | 30/1 | Existence of basic feasible solution | |

Affine set, affine combination of points | |||

9 | 31/1 | Convex sets - examples, closure properties, Convex Hull of a set | |

10 | 6/2 | Optimal solution is found at a bfs | |

convex hull of bfs = feasible solution (for closed bounded sets) | |||

11 | 7/2 | Finishing proof of convex hull of bfs = feasible solution | |

Observering the close relationship between geometric and algebraic view | |||

Observe through example neighbouring vertices | |||

12 | 13/2 | Traversing from one bfs to another bfs | |

Finding an initial bfs | |||

13 | 14/2 | The simplex algorithm | |

Proof of correctness | |||

14 | 24/2 | Tutorial | |

15 | 25/2 | Bipartite graph problem reduced to LP | |

Bit complexity - How big can the solution to an LP become? |

# | Problem | Due date |
---|