Instructor | Sepehr Assadi |

Credits | 3 units |

Schedule | Fridays 10:20 AM - 1:20 PM in PH-111 (Busch campus) |

Prerequisites | Undergraduate courses on algorithms, complexity theory, discrete mathematics, linear algebra, and probability; mathematical maturity. An advanced graduate course on algorithms (like CS 513 or 514) is strongly encouraged. |

Syllabus | The full course syllabus is available here. This webpage contains the highlights of course syllabus that are potentially updated as the semester progresses. |

Linear programming (LP) is an extremely general and popular method of optimization in various domains including computer science, operations research, engineering, and economics. This course primarily focuses on the theoretical foundations of LPs including modeling concepts, theory, algorithms, and theoretical applications.

The course is intended for computer science graduate students, as well as advanced graduate students from other disciplines, with the main purpose of
equipping the students with required background to use linear programming as part of their own research toolkit.

- Instructor: Sepehr Assadi
- Instructor Email: sepehr.assadi@rutgers.edu
- Lecture Schedule: Fridays 10:20 PM - 1:20 PM in PH-111 (Busch campus)
- Office hours: Fridays 2:00 PM to 3:00 PM in CORE 310 or on Zoom (email the Instructor for the Zoom link)

- Canonical LP Formulations
- Examples of LP: Shortest Path, Maximum Matching, Maximum Flows, Minimum Cost Flows, Spanning Trees, ...
- Cutting Plane Methods, Center of Gravity
- Convexity and Basics of Convex Optimization: Gradient Descent
- Special Cases: Covering and Packing LPs, Low-dimensional LPs, ...
- Fundamental Theorem of LP, Farkas's Lemma, ...
- Duality and Complementary Slackness
- The Simplex Algorithm
- Polynomial Time Algorithms: Ellipsoid and Interior-Point Methods
- Integer Programming, LP Relaxations, and Approximation Algorithms
- Basics of Matroid Theory and Combinatorial Optimization
- Advanced topics: LP Hierarchies, Extended Formulations, Smoothed Analysis, ...

- 40% Problem sets
- 20% Final Exam (take-home)
- 40% Scribe notes

# | Date | Topics | Lecture notes and Remarks |
---|---|---|---|

1 | Fri 09/09 | Introduction, Course Policy, Simple Examples of LPs | Lecture Notes 1 |

2 | Fri 09/16 | Basics of LPs: Standard Forms and Basic Feasible Solutions | Lecture Notes 2 |

3 | Fri 09/23 | The Simplex Algorithm | Lecture Notes 3 |

4 | Fri 09/30 | Duality in Linear Programming, Farkas Lemma | Lecture Notes 4 |

5 | Fri 10/07 | Low Dimensional LPs and Clarkson's Algorithm | Lecture Notes 5 |

6 | Fri 10/14 | Multiplicative Weight Update Method and Applications to Max-Flow | Lecture Notes 6 |

7 | Fri 10/21 | Convexity in Linear Programming | Lecture Notes 7 |

8 | Fri 10/28 | Introduction to Cutting Plane Methods: Center of Gravity | Lecture Notes 8 |

9 | Fri 11/04 | Ellipsoid Algorithm | Lecture Notes 9 |

10 | Fri 11/11 | More on Ellipsoid Algorithm and Applications | |

11 | Fri 11/18 | Gradient Descent and Applications | |

12 | Wed 11/23 | Newton Method and Intro to Interior Point Methods | |

13 | Fri 12/02 | Interior Point Methods | |

14 | Fri 12/09 | More on Interior Point Methods and Applications |

- Textbooks on Linear Programming (most relevant to the topics covered in our course):
- Introduction to Linear Optimization, by Bertsimas and Tsitsiklis;
- Understanding and Using Linear Programming, by Matoušek and Gärtner.

- Other related Books, Surveys, and Lecture Notes:
- Lecture notes for CMU’s course on Linear Programming and Semidefinite Programming, by Gupta, O’Donnell, and the scribes of 15-859E;
- Algorithms for Convex Optimization, by Vishnoi;
- Convex Optimization, by Boyd and Vandenberghe;
- Convex Optimization: Algorithms and Complexity, by Bubeck;
- Interior Point Polynomial Time Methods in Convex Programming, by Nemirovski;
- The Multiplicative Weights Update Method: a Meta-Algorithm and Applications, by Arora, Hazan, and Kale;

- Background on Algorithms and Probabilistic Analysis:
- Algorithm Design, by Kleinberg and Tardos;
- Randomized Algorithms, by Motwani and Raghavan;
- The Probabilistic Method, by Alon and Spencer;
- Concentration of Measure for the Analysis of Randomised Algorithms, by Dubhashi and Panconesi.

Two great introductory resources for LaTeX are A Short Introduction to LaTeX by Allin Cottrell (for general purpose LaTeX) and LaTeX for Undergraduates by Jim Hefferson (for undergraduates mathematics) accompanied by the following cheatsheet (note that this document use "\( MATH \)" notation compared to the perhaps more widely used "$ MATH $" -- both are completely fine in LaTeX). You can also use this wonderful tool Detexify by Daniel Kirsch for finding the LaTeX commands of a symbol (just draw the symbol!).

If you are interested in learning more about LaTeX (beyond what is needed for this course), check the Wikibook on LaTeX and the Wikibook on LaTeX for Mathematics.

If you witness or experience racism, discrimination micro-aggressions, or other offensive behavior, you are encouraged to bring it to the attention to the undergraduate program director and/or the department chair. You can also report it to the Bias Incident Reporting System

Masks should conform to CDC guidelines and should completely cover the nose and mouth.

If you are feeling sick, or suspect you may have been exposed to COVID-19, do not come to the class. Arrangements will be made for students who are not able to attend class because of an illness or quarantine.