Week 1: Set Cover, Greedy Algorithms, Linear Programs
- Lecture 1 (Aug 30, AG). Introduction + Set Cover.
(handwritten
notes)
- Ron Graham's
1972 paper
on Parallel Machine Scheduling.
- David Johnson's
1979 paper
on Approximation Algorithms, with algorithms Set Cover etc.
- Neal
Young's entry
on Set Cover in the Encyclopedia of Algorithms
(with many references).
- Lecture 2 (Sep 1, AG). Set Cover and Max-Coverage: LP-based techniques.
(handwritten
notes)
- Chapter 1 of the Williamson-Shmoys book covers most of
the set-cover algorithms we covered.
Their randomized rounding only
gives feasibility with high probability. I prefer the method that picks set to clean up at the end.
- The deterministic rounding is based on ideas from the
Pipeage Rounding framework of Ageev and Sviridenko.
- Lecture 3 (Sep 3, AG). Hardness of Approximating Max-Coverage.
(handwritten
notes)
Week 2: Max-Cut, Semidefinite Programming, Rounding/Integrality Gaps
- Sep 6. Labor day holiday!!
- Lecture 4 (Sep 8, PK). Max-Cut: The Goemans Williamson Algorithm (handwritten
notes)
- Lecture 5 (Sep 10, PK). Max-Cut: Integrality Gaps, Rounding Gaps (handwritten
notes)
(handwritten
notes)
- The original Feige-Schechtman (2001) paper.
Week 3: Sparsest Cut: Linear Programming, Metric Embeddings, and Spectral Partitioning
- Lecture 6 (Sep 13, AG). Sparsest Cut: Region Growing and the Leighton Rao LP
(handwritten
notes)
- Lecture 7 (Sep 15, AG). Sparsest Cut: Metric Embeddings
(handwritten
notes)
- Lecture 8 (Sep 17, AG). Sparsest Cut: Spectral Partitioning and
the Cheeger Bounds
(handwritten
notes)
Week 4: Spectral Algorithm for Max-Cut, The Arora-Rao-Vazirani Algorithm for Sparsest Cut
- Lecture 9 (Sep 20, PK): Max-Cut and Eigenvalues of Graphs (handwritten
notes)
- Lecture 10 (Sep 22, PK). The Arora-Rao-Vazirani Algorithm I (handwritten
notes)
- Lecture 11 (Sep 24, PK). The Arora-Rao-Vazirani Algorithm II (handwritten
notes)
- The original Arora-Rao-Vazirani paper.
- Lee's simplified and tighter structure theorem.
- Naor-Rabani-Sinclair with another perspective on ARV structure theorem.
- Rothvoss's notes on the ARV algorithm.
- Pollard's exposition on Gaussian Processes and Proofs of Borell's inequality.
Week 5: Combinatorial and LP-based Techniques: Facility
Location Problems.
- Lecture 12 (Sep 27, AG). Local Search Algorithms.
(handwritten
notes)
- Lecture 13 (Sep 29, AG): LP Rounding-based Algorithms.
(handwritten
notes)
- See Sections 4.5 and 5.8 of the Williamson-Shmoys book.
- Lecture
notes
from the 2008 version of the course.
- Lecture 14 (Oct 1, AG). Hardness for Facility Location. Primal-Dual Algorithms.
(handwritten
notes, and hardness)
- Animation for the primal-dual algorithm.
- See Sections 7.6-7.7 of the Williamson-Shmoys book.
- Lecture
notes
from the 2008 version of the course.
Week 6: Hardness of Approximation
- Lecture 15 (Oct 4, PK): Introduction to Hardness of Approximation, Hardness of Vertex Cover, Sparsest Cut (handwritten
notes.)
- Lecture 16 (Oct 6, PK): Unique Games Conjecture, Basic Boolean Fourier Analysis (handwritten
notes.)
- Lecture 17 (Oct 8, PK): UGC-Based Hardness from Dictator vs Spread-Out Function Tests I (handwritten
notes.)
Week 7: Wrap Up Hardness. Other Techniques: More on LPs (LP structure, Strengthening LPs)
- Lecture 18 (Oct 11, PK): UGC-Based Hardness from Dictator vs Spread-Out Function Tests II (handwritten
notes.)
- Lecture 19 (Oct 13, AG). Scheduling Problems: LP Structure, Strengthening LPs (handwritten notes)
- See chapters 4.1, 4.2 of the [WS10] book.
- A survey by Karger, Stein, and Wein on scheduling algorithms.
- Lecture 20 (Oct 15, AG). Iterated Rounding (handwritten notes)
- See chapters 11 of the [WS10] book.
- A monograph on iterated rounding by Lap Chi Lau, R. Ravi, and
Mohit Singh.
Week 8: Sum-of-Squares SDP Hierarchy
- Lecture 21 (Oct 18, PK): Strengthening Convex Relaxations: SDP Hierarchies I (handwritten notes)
- Notes from the CMU course on "Proofs vs Algorithms: The Sum-of-Squares Method".
- Online notes on Sum-of-Squares SDPs.
- Lecture 22 (Oct 20, PK): Strengthening Convex Relaxations: SDP Hierarchies II (handwritten notes, same as above)
- Lecture 23 (Oct 22, PK): Strengthening Convex Relaxations: SDP Hierarchies III (handwritten notes, same as above)
Week 9: Behind the Scenes: Gaussian Elimination, The Ellipsoid method, and Interior Point Methods
- Lecture 24 (Oct 25, AG): Gaussian Elimination, Linear Systems,
and Related Topics (handwritten notes
from Pravesh, Anupam)
- Edmonds' paper on Gaussian Elimination.
- Notes
from Laci Lovasz and Peter Gacs.
- How ordinary elimination became Gaussian
elimination:
a historical
survey of this classical idea, by Joseph Grcar
(arxiv).
- Bunch
and Hopcroft
show that Matrix Inversion
and LU factorization have the same complexity as (Fast) Matrix Multiplication.
- Swastik
Kopparty's course
on Algorithmic Number Theory
covers Elimination, solving linear systems over
the integers, and other fun numerical problems.
- Lecture 25 (Oct 27, AG). The Ellipsoid Algorithm, this time
without Ellipsoids! (handwritten
notes from page 5 onwards, additional
notes)
- Lecture 26 (Oct 29, AG). Eigenvalue Computations. (handwritten
notes)
- See these books
by Lloyd
Trefethen
and David Bau (very readable),
or Gene
Golub
and Charlie van Loan (more encyclopedic).
- Applied-math/numerical analysis-oriented top
ten algorithm lists
(here
and here)
contain both
matrix
factorizations (e.g., QR)
and
the QR
algorithm (jupyter notebooks).
Other algorithms include (quasi-)Newton methods, the simplex method, FFTs, Kalman
filters, Pagerank, Monte Carlo methods, JPEG, and Krylov
subspace methods.
The course page linked above has other references, notes,
papers, notebooks.
- Worried about the bit complexity? Accuracy and Stability of Numerical Algorithms by Nick Higham.
- Optional: Understanding the QR algorithm
and The QR
algorithm revisited, both by David Watkins.
- Two Classic Texts: The
Symmetic Eigenvalue Problem
by Beresford Parlett, and the Algebraic Eigenvalue Problem
by J.H. Wilkinson
(Partial) Week 10: Wrapup!
- Lecture 27 (Nov 1, AG/PK). Wrap-up and Future Directions.
End of course!
Description
The area of approximation algorithms is aimed at giving provable
guarantees on the performance of heuristics for hard problems. Over
the years, many techniques have been developed to obtain such
algorithms. These include techniques such as linear and convex
programming, use of randomness, and metric embeddings. Along with the
algorithmic approaches, techniques have been developed to show
inapproximability, where we show limits to how well problems can be
approximated (using some restricted set of techniques, or assuming
conjectures like P neq NP or UGC). The aim of the course is to expose
students to ideas from both these threads of research.
The focus of the course will be on more recent techniques and
directions of research, and on getting tight upper and lower
bounds. Since a significant fraction of such results involve
computing on inputs that are naturally thought of as vectors of real
numbers, we will discuss how these approximate representations
affects the running time and the performance guarantees of the
algorithms we design; this will take us on a detour into the algorithmic
aspects of numerical analysis.
A version of this course was taught in Spring 2008 (by
Gupta and O'Donnell). Much
as in that version, the
Fall 2021 version will also cover upper and lower bounds for approximation algorithms.
However, we will cover a slightly different set of topics (reflecting the change in
instructors and their tastes, as well as changes in topics and trends within the area).
The digression into numerical analysis will be an entirely new addition to the course.
Prerequisites:
Mathematical maturity is a must. We will assume
a solid grounding in algorithms, complexity, probability, and linear algebra. We urge you to brush up on them
if you are rusty --- we can point you to books or lecture notes on
them. The use of linear algebra and probability is ubiquitous across
all of CS, just like the use of algorithms. Learning those topics will
not be a waste of your time, whether you take this course or not.
If you are not sure whether you have the right
algorithms/complexity/basic math background, feel free to speak to
us before you decide to take the course.
Textbook:
The "two
Davids" textbook by
David Williamson and David Shmoys is a good introduction to the
area, it is available both online and in print. Papers and notes will be distributed as necessary.
Maintained by Anupam Gupta and Pravesh Kothari.