# CS 520: Combinatorial optimization

January 2020

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

## Time and Place

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

## Pre-requisite

Algorithms and Linear algebra course.

## Books

• Linear programming by Matousek

## Reference

• 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

## Syllabus (not necessarily in this order)

• 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.

## Course Schedule

# 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?

## Assignments

# Problem Due date