Course Contents
Matching, Linear Programming Basics, LP Duality, Primal Dual Approach.
LP in Combinatorial Optimization: Shortest Path, Bipartite Matching, Maximum Flow, General Matching.
Approximation Algorithms for NP-hard problems: Max SAT, Steiner tree, Max Cut via Semidefinite Programming
Online Algorithms: adwords problem
Interior Point Method for Linear Programming
Convex programming, duality, Gradient descent for max flow or matching.
Matroids, Matroid intersection
Pre-requisites: You are expected to know basics of algorithms (CS218/CS601), linear algebra and graph theory.
Grading: Two assignments (5+5), Paper Presentation (20), Two exams (25+45).
References
Alexander Schrijver, Combinatorial Optimization Polyhedra and Efficiency, Vol A,B. Springer, 2004 (shared on Moodle).
David B. Shmoys and David P. Williamson, The Design of Approximation Algorithms.
Niv Buchbinder and Joseph Naor The design of competitive online algorithms via a primal-dual approach
Nisheeth K. Vishnoi. Algorithms for Convex Optimization
Stephen Boyd (Author), Lieven Vandenberghe. Convex Optimization
Presentations by students
Extended formulations for spanning tree polytopes by Kalp Vyas and Lakshya Gupta
Lower bounds on LP extensions by Aaryan Gupta, Parth Dwivedi, Sai Teja Varanasi
Total Unimodularity and Integrality of LP optimal by Anvay, Ramsundar
Min Max Game Theory On-line Prediction and Boosting by Keerthana Reddy, Paidi Venkata Ganesh
Zero Sum games and LP Duality by Guramrit Singh, Parth Pujari
Perfect Matching Polytope for general graphs and its Separation Oracle by Siddharth Mahesh Patil and Ankan Sarkar
Minimum bounded degree spanning trees by Alan babu, Ebrahim Sohail Haris, Yash Patil
Multiplicative Weights Update Algorithm by Lokesh, Rahul Deepak, Raja Gopal
Multicut and Integer Multicommodity Flow in Trees by Yash Sadhwan and Hritiz Gogoi
Minimum Cost Flow Primal-Dual Algorithm by Ayyapu Ruthvika, Dhananjay Kejriwal, Mothika Gayathri Khyathi
Matroids and the greedy algorithm, Matroid polytope by Himanshi Singh and Jaya Bharti
Graph structure of two player games by Akshay Gaikwad
Insights into the core of the assignment games by Ashwin Abraham, Harshit Morj, and Soham Joshi
Feedback vertex set by Likith Rajesh, Sanchit Jindal, and Virendra Kabra
Spanning tree and minimum cost arborescence by Peram Ankshita, Sirigudi Meghana, and Vishwesh Kandukuri
Lectures and Homeworks
Homework (Lecture 1-13)
Lecture 1, 2 (Aug 1, 4) Matching problem and Edmonds' blossom algorithm. (Ref: Schrijver Section 24.2)
Lecture 3 (Aug 8) Linear programs, Integer LPs and relaxations for combinatorial problems.
Lecture 4 (Aug 11) Polyhedron. Optimal set of points form a face.
Lecture 5 (Aug 18) Corners of a polytope. Caratheodory's theorem.
Lecture 6 (Aug 22) Convex hull of finitely many points. Fourier Motzkin elimination. Feasibility vs. Optimization.
Lecture 7 (Aug 25) Farkas' Lemma via FM elimination. Feasibility in coNP.
Lecture 8 (Aug 29) Dual LP. Weak and Strong duality theorems.
Lecture 9 (Sep 1) Dual LP of various forms. Economic interpretation of dual. Shortest path LP, dual LP, Dijkstra's algorithm.
Lecture 10 (Sep 5) Minimum weight Bipartite matching: primal dual algorithm
Lecture 11 (Sep 8) LPs for spanning tree, non-bipartite matching. Minimum vertex cover.
Lecture 12 (Sep 12) Extended LP formulation for spanning trees. 2-approximation of minimum weight vertex cover via primal dual.
Lecture 13 (Sep 15) Two player zero sum games and LP duality.
Homework (Lecture 14-20)
Lecture 14, 15, 16 (Sep 26, 29, Oct 3) Steiner tree, Steiner forest, greedy approximation algorithms, LP primal-dual approximation algorithm
Ref: Chapter 22 in Vazirani book, or Section 7.4 in Willimason-Shmoys book
Lecture 17, 18 (Oct 6, 10) LP rounding. Min vertex cover. Max weight satisfiability problem. Greedy and Randomized approaches. Deterministic algorithm using method of conditional expectation.
Ref: Williamson Shmoys book Section 5.1 - 5.5
Lecture 19, 20, 21 (Oct 13, 17, 20) Semidefinite programming. Max Cut approximation based on SDP.
Ref: Williamson Shmoys book Section 6.1 - 6.2
Homework (Lecture 22-)
Lecture 22 (Oct 27) Simplex algorithm. Ref: CLRS chapter 29.
Lecture 23, 24 (Oct 31, Nov 3) Ellipsoid Algorithm.
Lecture 25, 26 (Nov 7, 10) Karmarkar's Interior point method.
Ref: Chapter 10, Vishnoi.