CS602: Applied Algorithms : Linear Programming in Combinatorial Optimization (2019-20 Sem II)

Course Contents

The course will start with basics of linear programming and duality. Then we will see applications of LP in combinatorial optimization, problems like matching, maximum flow, minimum cut, matroids, submodular optimization etc. We will see examples where LP is used in designing approximation algorithms for hard problems and online algorithms. Other topics we might cover -- Linear programming extended formulations, semi-definite programming and continuous methods for combinatorial problems.

Pre-requisites: You are expected to know basics of algorithms (CS218/CS601), linear algebra and graph theory.

Grading: Class participation (includes scribing lecture notes) , Assignments and Quizzes (in class) (30%), Mid-sem(30%), End-sem + possibly a paper presentation (40%).

Course Timings: Mon 10:35-11:30, Tue 11:35-13:00, Thu 8:30-9:25. SIC201, KreSIT.

Office Hours: Monday, 11:30-12:30

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.
Vijay Vazirani, Approximation Algorithms, Springer, 2003
Niv Buchbinder and Joseph Naor The design of competitive online algorithms via a primal-dual approach

Homework 1 Homework 2 Quiz 1 Homework 3 Mid Sem Homework 4 Homework 5

Lectures:

Linear Programming (You can see Lap Chi Lau's Course Notes and Lecture 16 here)

Lecture 1 Tex (Jan 13): Linear programming: standard forms, equivalence between them. Polytopes, Faces, Vertices.
Lecture 2 Tex(Jan 20): Defining a face of a polyhedron. Set of points optimizing a linear function form a face.
Lecture 3 Tex (Jan 21): Characterizing a face as optimal set of points. Corners/Vertices of the Polyhedron: three definitions.
Lecture 4 Tex (Jan 23): Vertices to Faces and vice versa. Fourier Motzkin Elimination.

Linear Programming Duality (See Lecture 16,17 here)

Lecture 5 Tex (Jan 27): Feasibility vs. Optimization. Bit complexity of feasible/optimal solutions. Exponetial time algorithm. NP.

Discussion and Homework

Lecture 6 Tex (Jan 28): Feasibility in coNP. Farkas' Lemma.
Lecture 7 Tex (Jan 30): LP weak duality. NP and coNP.
Lecture 8 Tex (Feb 3): LP strong duality. Various forms.

LP for Combinatorial Optimization (see these notes for primal dual schema for bipartite matching)

Lecture 9 Tex (Feb 4): Expressing shortest path problem as an LP. Its dual LP and the thread-pulling interpretation.
Lecture 10 Tex (Feb 6): Maximum Bipartite Matching as LP and its dual Minimum vertex cover.
Lecture 11 Tex (Feb 11): Complementary Slackness and Primal-Dual Schema (can see 5.13 in Schrijver's book).
Lecture 12 Tex (Feb 13): Augmenting path algorithm for bipartite maximum matching. Primal-Dual Schema.
Lecture 13 Tex (Feb 20): Primal-Dual Schema for Min weight Perfect Matching in Bipartite graphs.

Primal Dual for Approximation algorithms (see this Chapter)

Lecture 14 Tex (Mar 2): Steiner tree. Soap film.
Lecture 15 Tex (Mar 5): Steiner tree. Primal and Dual LP.
Lecture 16 Tex (Mar 12): Primal-dual algorithm for Steiner tree/forest.
Lecture 17 Tex Video (Mar 17): Analysis of the Primal-dual algorithm for Steiner tree/forest.
Lecture 18 - I Tex1 Lecture 18 - II Tex2 Video (Mar 24): Solving Linear Programs: Simplex, Ellipsoid, Interior Point.
Lecture 19 - I Tex Lecture 19 - II Tex Video 1 Video 2 (Mar 28): LP rounding, Linearity of Expectation, Approximation algorithm for Max SAT via LP.