CS602: Applied Algorithms : Convex Programming in Combinatorial Optimization (2020-21 Sem II)

Course Contents The course will start with basics of linear programming and duality. We will also talk about semidefinite programming and more generally about convex programming. Then we will see applications of LP and SDP in combinatorial optimization, problems like matching, maximum flow, minimum cut, matroids, submodular optimization, graph coloring etc. We will see examples where LP and SDP is used in designing approximation algorithms for hard problems and online algorithms, for example Steiner Tree, Max Cut etc. Other topics we might cover -- Linear programming extended formulations, and continuous methods for combinatorial problems.

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

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

• Nisheeth K. Vishnoi. Algorithms for Convex Optimization

Lecture Videos:

• Google drive link

• Introduction to the Course Slides

Week 1 (Jan 11-17) Linear Programming

• Jan 11 (Introduction to Linear Programming)

• Jan 12 - part 1 (LP standard forms)

• Jan 12 - part 2 (Geometric Perspective to LP)

• Jan 14 - part 1 (Optimizing points form a face)

• Jan 14 - part 2 (Minimal face containing an optimal point is also optimal)

• Jan 14 - part 3 (There is one optimal face)

• Slides Week 1

• Homework Week 1

Week 2 (Jan 18-24) LP Geometric Perspective

• Jan 18 - part 1 (Last week recap)

• Jan 18 - part 2 (Corners of a polyhedron)

• Jan 18 - part 3 (Equivalence between three definitions)

• Jan 19 - part 1 (Equivalence between definitions continued)

• Jan 19 - part 2 (Polytope is a Convex Hull)

• Jan 19 - part 3 (Convex hull of k points is a polytope)

• Jan 21 - part 1 (Fourier Motzkin elimination)

• Jan 21 - part 2 (An inefficient algorithm for LP)

• Jan 21 - part 3 (LP feasibility and optimization)

• Slides Week 2

• Homework Week 2

Week 3 (Jan 25-31) LP in NP and coNP

• References for LP basics and duality 1 2 3

• Jan 25 - 1 (Feasibility reduces to Optimization)

• Jan 25 - 2 (Feasibility in NP)

• Jan 25 - 3 (Feasibility in coNP)

• Jan 28 - 1 (Farkas' Lemma and its proof)

• Jan 28 - 2 (Lower and upper bounding optimal value)

• Slides Week 3

• Homework week 3

Week 4 (Feb 1 - 7) LP Duality

• Feb 1 - 1 (Dual LP and weak duality)

• Feb 1 - 2 (Strong Duality, Various forms)

• Feb 2 - 1 (Writing dual LP for various forms)

• Feb 2 - 2 (LP for Shortest Path)

• Feb 4 (Shortest path dual LP, Integral optimal)

• Slides Week 4

Week 5 (Feb 8-14) Complementary Slackness and Primal-Dual Schema

• Feb 8 (Complementary Slackness)

• Feb 9 - 1 (Primal-dual schema, Shortest Path)

• Feb 9 - 2 (Min weight bipartite matching - LP and Dual)

• Feb 11 - 1 (Primal-Dual Schema for Min weight bipartite matching)

• Feb 11 - 2 (Primal-Dual Schema for general LP)

• Slides Week 5

• Homework Week 5

Week 6 (Feb 15-21) Steiner Tree/Forest: Primal-Dual approximation

• Reference: Chapter 22 in Vazirani book, or Section 7.4 in Willimason-Shmoys book

• Feb 15 (Steiner Tree Problem)

• Feb 16 -1 (MST based Approximation for Steiner Tree)

• Feb 16 - 2 (Integer Program for Steiner Tree)

• Feb 18 - 1 (Steiner Tree/Forest LP)

• Feb 18 - 2 (Steiner Tree/Forest Dual LP)

Week 7 (Mar 4-11) Steiner Tree/Forest continued

• Mar 4 - 1 (Steiner Tree LP Recap)

• Mar 4 - 2 (Primal-dual schema for Steiner Tree: a high level picture)

• Mar 4 - 3 (Primal dual Schema: running through a simple example)

• Mar 8 - 1 (Increasing the dual variables in an arbitrary order)

• Mar 8 - 2 (Increasing the dual variable systematically: case of two terminals)

• Mar 9 - 1 (Primal Dual Algorithm for multiple terminals)

• Mar 9 - 2 (Analysis of the Primal-dual)

• Mar 11 - 1 (Finishing the Analysis of Primal Dual)

• Slides Steiner Tree

• Homework Steiner Tree

Week 8 (Mar 11-17) Online Algorithms: Ski Rental

• Reference: Chapter 3,4 in Buchbinder Book

• Mar 11 - 2 (Introduction to online algorithms)

• Mar 15 - 1 (Ski Rental - Deterministic and Randomized strategies)

• Mar 15 - 2 (Ski Rental - LP and Dual LP)

• Mar 16 - 1 (Ski Rental Primal Dual Algorithm)

• Mar 16 - 2 (From Fractional solution to Randomized Strategy)

• Ski Rental Slides

Week 9 (Mar 18-22) Online Algorithms: Ad Allocation

• Reference: Chapter 10 in Buchbinder Book

• Mar 18 - 1 (Online Ad Allocation: Introduction)

• Mar 18 - 2 (Writing the LP)

• Mar 22 - 1 (LP and Dual LP for ad allocation)

• Mar 22 - 2 (Ad allocation algorithm based on primal dual)

• Ad Allocation Slides

Week 10 (Mar 23-Apr 1) Approximation Algorithms via LP: Maximum Satisfiability

• Reference: Williamson Shmoys book Section 5.1 - 5.5

• Mar 23 - 1 (Approximation algorithms via LP rounding)

• Mar 23 - 2 (Max Satisfiability: simple randomized algorithm)

• Mar 25 - 1 (Max SAT - 1/2 approx randomized algorithm)

• Mar 25 - 2 (Max SAT - 1/2 approx deterministic algorithm)

• Mar 30 - 1 (Max SAT Linear Program formulation and Rounding)

• Mar 30 - 2 (Max SAT - Expected Weight)

• Apr 1 - 1 (Finishing the analysis of expected weight)

• Apr 1 - 2 (Derandomization, Better Approximation, Integrality Gap)

• Maximum Sastisfiability slides

Week 11-13 (Apr 5-20) Algorithms for solving Linear Programs

1. Simplex Method

   • Reference for Simplex

   • Apr 5 - 1 (Simplex Algorithm)

   • Apr 5 - 2 (Simplex Cont.)

   • Apr 6 - 1 (Simplex Q&A)

   • Simplex Method Slides

2. Ellipsoid Method

   • Reference for Ellipsoid method

   • Apr 6 - 2 (Ellipsoid Algorithm - Introduction)

   • Apr 6 - 3 (Separating Hyperplane)

   • Apr 8 - 1 (Consequences of Separating Hyperplane Theorem)

   • Apr 8 - 2 (Ellipsoid: generalized sphere)

   • Apr 8 - 3 (Ellipsoid Algorithm: input, output, and promises)

   • Apr 12 - 1 (Ellipsoid Algorithm Outline)

   • Apr 12 - 2 (Finding an ellipsoid containing half sphere)

   • Apr 15 - 1 (Ellipsoid method for LP: upper bounding R)

   • Apr 15 - 2 (Ellipsoid method for LP: lower bounding the volume)

   • Ellipsoid Method Slides

3. Interior Point Method

   • Reference: Chapter 9 and 10 in Vishnoi's book

   • April 19 - 1 (Interior point method, Gradient descent)

   • Apr 19 - 2 (Newton's Root finding)

   • Apr 20 - 1 (Convergence of Newton's root finding)

   • Apr 20 - 2 (Barrier function, Interior Point Algorithm)

   • Apr 20 - 3 (Starting point of the central path)

   • Interior Point Method Slides