Course Contents
Matching, Linear Programming Basics, LP Duality, Primal Dual Approach.
LP in Combinatorial Optimization: Shortest Path, Bipartite Matching, Maximum Flow General Matching. Primal Dual Algorithm.
Convex Programming, Duality, Matching/Max flow via Gradient Descent
Interior Point Method for Linear Programming, Matching/Max flow
Approximation Algorithms for NP-hard problems: Max SAT, Max Cut via Semidefinite Programming
Matroids, Matroid intersection
Pre-requisites: You are expected to know basics of algorithms (CS218/CS601), linear algebra and graph theory.
Course Meetings: Mon, Thu 17:30-18:55 Meeting link Password: 3Xqjg47Tz85
References
Alexander Schrijver, Combinatorial Optimization Polyhedra and Efficiency, Vol A,B. Springer, 2004.
David B. Shmoys and David P. Williamson, The Design of Approximation Algorithms.
Nisheeth K. Vishnoi. Algorithms for Convex Optimization
Stephen Boyd (Author), Lieven Vandenberghe. Convex Optimization
Lecture 1 video (Jan 6) LP definition, various forms, LP relaxation for maximum independent set
Lecture 2 video (Jan 10) Set of points optimizing a linear function form a face of the polyhedron
Lecture 3 video (Jan 13) Corners of a polytope, Caratheodory theorem, a polytope is a convex hull.
Lecture 4 video (Jan 17) Fourier Motzkin Elimination, The right LP for a combinatorial problem.
Lecture 5 video (Jan 20) Bipartite perfect matching polytope, LP feasibility and optimization.
Lecture 6 video (Jan 24) Farkas' Lemma, proof via FM elimination, different forms. Lower/upper bounds on LP opt.
Lecture 7 video (Jan 27) Dual LP formulation, weak and strong duality theorems.
Lecture 8 video (Jan 31) Dual LP for various forms, Economic interpretation of dual variables.
Reading assignment Augmenting path algorithm for bipartite matching and proof of Hall's theorem
Lecture 9 video (Feb 3) Shortest path LP and dual LP, Complementary slackness.
Lecture 10 video (Feb 7) Primal dual algorithm for minimum weight perfect matching in bipartite graphs.
Lecture 11 video (Feb 11) Analyzing primal dual for BPM, LP descriptions for various combinatorial problems.
Lecture 12 video (Feb 14) Minimum weight vertex cover: 2-approximation via primal dual
Lecture 13 video (Feb 17) Nash equilibrium in 2-player zero-sum games via LP duality Reference
Lecture 14 video (Feb 28) Steiner forest: LP and primal-dual overview.
Lecture 15 video (Mar 3) Steiner forest: primal-dual algorithm and 2-approximation analysis
Intereseting video showing how to solve Euclidean Steiner tree using soap solution
MAXSAT LP Slides MAXCUT SDP slides Homework (Lectures 16-19)
Lecture 16 video MAXSAT: randomized algorithm for 1/2-approximation, rounding an LP.
Lecture 17 video MAXSAT: rounding the LP, integrality gap
Lecture 18 video Introduction to semidefinite programming (SDP)
Lecture 19 video MAXCUT via rounding SDP
Lecture 20 video Simplex algorithm
Lecture 21 video Ellipsoid Method
Lecture 22 video Ellipsoid Method: analysis
Lecture 23 video Gradient descent (Reference: Vishnoi Chapter 6)
Lecture 24 video Gradient descent for perfect matching, Newton's method of root finding
Lecture 25 video Barrier function for LPs (Ref: Boyd and Vandenberghe Chapter 9)
Lecture 26 video Interior point method for LPs (Ref: Vishnoi Chapter 10)