||Fridays 10:20 AM - 1:20 PM in
PH-111 (Busch campus)
|| 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.
||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: email@example.com
- 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)
This course has no recitation sections.
COVID-19 Protocols: In accordance with Rutgers' policy, masks must be worn during class meetings
(According to Rutgers' updated policy, masks are no longer required in classes).
The following is a tentative list of topics (not necessarily in order) that will be covered in this course.
- 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, ...
Along the way, we will learn about various algorithmic, analytic, and structural results in the context of linear programming that are widely applicable
to other areas of theoretical computer science as well.
The final grade for the course will be based on the following weights:
- 40% Problem sets
- 20% Final Exam (take-home)
- 40% Scribe notes
More details on the grading is posted in the course syllabus
The schedule below the red line
and subject to change.
||Lecture notes and Remarks
|| Fri 09/09
|| Introduction, Course Policy, Simple Examples of LPs
|| Lecture Notes 1
|| Fri 09/16
|| Basics of LPs: Standard Forms and Basic Feasible Solutions
|| Lecture Notes 2
|| Fri 09/23
|| The Simplex Algorithm
|| Lecture Notes 3
|| Fri 09/30
|| Duality in Linear Programming, Farkas Lemma
|| Lecture Notes 4
|| Fri 10/07
|| Low Dimensional LPs and Clarkson's Algorithm
|| Lecture Notes 5
|| Fri 10/14
|| Multiplicative Weight Update Method and Applications to Max-Flow
|| Lecture Notes 6
|| Fri 10/21
|| Convexity in Linear Programming
|| Lecture Notes 7
|| Fri 10/28
|| Introduction to Cutting Plane Methods: Center of Gravity
|| Lecture Notes 8
|| Fri 11/04
|| Ellipsoid Algorithm
|| Lecture Notes 9
|| Fri 11/11
|| More on Ellipsoid Algorithm and Applications
|| Fri 11/18
|| Gradient Descent and Applications
|| Lecture Notes 11
|| Wed 11/23
|| Newton Method and Intro to Interior Point Methods
|| Lecture Notes 12
|| Fri 12/02
|| Interior Point Methods
|| Fri 12/09
|| More on Interior Point Methods and Applications
There is no official textbook for this course and all required materials will be posted on this webpage.
The following is a list of some helpful supplementary materials (this list is by no means comprehensive):
- 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.
You can download LaTeX for free here
. For the purpose of this course, you do not even need to install LaTeX and
can instead use an online LaTeX editor such as Overleaf
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
the Wikibook on LaTeX for Mathematics
Rutgers Computer Science Department is committed to creating a consciously anti-racist, inclusive community that welcomes diversity in various dimensions
(e.g., race, national origin, gender, sexuality, disability status, class, or religious beliefs).
We will not tolerate micro-aggressions and discrimination that creates a hostile atmosphere in the class and/or threatens the well-being of our students.
We will continuously strive to create a safe learning environment that allows for the open exchange of ideas and cherished freedom of speech, while also
ensuring equitable opportunities and respect for all of us. Our goal is to maintain an environment where students, staff, and faculty can contribute without the fear
of ridicule or intolerant or offensive language.
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
In order to protect the health and well-being of all members of the University community, masks must be worn by all persons on campus when in the presence of others (within six feet) and in buildings in non-private enclosed settings (e.g., common workspaces, workstations, meeting rooms, classrooms, etc.). Masks must be worn during class meetings; any student not wearing a mask will be asked to leave.
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.