CS 514: Round(ing) Set Cover 80 Ways
Fall 2026, Rutgers University
Time and Location
Wednesday 12:10pm – 3:10pm, SEC 208
Instructor
Roie Levin, Core 306
Course Description
This course is a graduate-level survey of topics in online and approximation algorithms. We will use Set Cover as a sandbox problem on which to illustrate a variety of modern techniques. This course is intended for PhD students with mathematical maturity, and there will be a final project at the end of the course.
Why Set Cover? Isn’t that just one niche problem?
Set Cover is the following combinatorial problem: given a collection of sets $\mathcal{S}$ over ground set $U$, find the smallest subcollection of sets $\mathcal{C} \subseteq \mathcal{S}$ that covers $U$, i.e. such that $\bigcup_{S \in \mathcal{C}} S = U$.
To understand why this problem is so fundamental, observe that it is equivalent to
\[\min \{ \langle \vec 1, x \rangle \mid Ax \geq \vec 1, \ \ x \in \mathbb{Z}^n_{\geq 0} \}\]where $A$ is a $0 / 1$ matrix.
In other words, Set Cover is exactly integer programming with binary constraint coefficients, and as such is often the prototypical combinatorial optimization problem. Studying algorithms in simple settings will allow us to distill key ideas in their cleanest form.
(Tentative) Schedule
| Date | Topic | Lecture Notes | References |
|---|---|---|---|
| Sep 02 | Course Overview and Intro to Set Cover | ||
| Sep 09 | Greedy, Linear Programming, Randomized Rounding | ||
| Sep 16 | Fast(er) Offline Algorithms | ||
| Sep 23 | Local Search | ||
| Sep 30 | Structured Families: Total Unimodularity, Network Design, VC Dimension | ||
| Oct 07 | Generalizations: Submodularity, Node-Weighted Network Design | ||
| Oct 14 | Online Algorithms, Information Projections | ||
| Oct 21 | Random-Order Algorithms | ||
| Oct 28 | Stochastic, $p$-sample, Prophet Algorithms | ||
| Nov 04 | Dynamic Algorithms | ||
| Nov 11 | Streaming Algorithms | ||
| Nov 18 | Parallel Algorithms | ||
| Nov 25 | NO CLASS – Thanksgiving | ||
| Dec 02 | Hardness of Approximation | ||
| Dec 09 | Final Presentations |