CMU 15-854(B): Advanced Approximation Algorithms, Fall 2021

Lecturers: Anupam Gupta (anupamg ate cs), Pravesh Kothari (praveshk ate cs).

TAs: Xinyu Wu (xinyuwu ate cmu dit edu)

Office hours: Anupam (Wed 3-4 pm, GHC 7203), Pravesh (Mon 1-2 pm, GHC 7105), Xinyu (Wed 4:30-5:30 on Zoom).

Location: GHC 4211, Mon/Wed/Fri 10:10-11:30.

Piazza: piazza.com/cmu/fall2021/15854b/home

Gradescope: https://www.gradescope.com/ (signup code on Piazza, if needed)

Announcements

• Please note that we meet three days a week (M/W/F 10:10-11:30) for the first ten weeks of the semester.
• Lectures begin on August 30.

Homeworks

• Homework 0 (due Friday, Sep 3)
• Homework 1 (due Wednesday, Sep 22)
• Homework 2 (due Wednesday, Oct 6)
• Homework 3 (due Monday, Oct 25)
• Homework 4 (due Friday, Dec 3)

Lectures

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)
  • The PCP theorem was proved by Arora, Lund, Motwani, Sudan, and Szegedy, and Arora and Safra in 1991/92. A combinatorial proof was given by Irit Dinur in 2006.
  • The parallel repetition theorem was due to Ran Raz.
  • The original papers: Lund-Yannakakis, Feige, Dinur-Steurer.
    The first hardness of approximation for set-cover (and hence max-coverage) was by Lund and Yannakakis.
    Feige gave the tight approximation factors, but the set-cover reduction was under a slightly stronger assumption.
    Dinur and Steurer finally proved the hardness assuming P neq NP.



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)
  • Chapter 6 (and section 6.1) of [Williamson-Shmoys] covers the max-cut algorithm and rounding.
  • The original Goemans-Williamson paper.
  • Some deterministic rounding algorithms [Engebretsen Indyk O'Donnell (2002), Sivakumar (2003)] with the same guarantees.
  • An improvement on GW for bounded degree graphs by Feige, Karpinski and Langberg.
  • O'Donnell and Wu on improving GW to a better (and sharp, if the UGC is true) (c,s)-approximation curve.
  • Lower bounds on linear programs for Max-Cut: Chan, Lee, Raghavendra, Steurer and Kothari, Meka, Raghavendra.


• 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)
  • The Leighton-Rao paper.
  • Chapter 8 of [Williamson Shmoys] talks about region growing in detail.
  • A survey on Approximations for Cut Problems by David Shmoys gives the history, and discusses divide-and-conquer applications.
  • Some notes on the Leighton-Rao Rounding from Rajmohan Rajaraman.


• Lecture 7 (Sep 15, AG). Sparsest Cut: Metric Embeddings (handwritten notes)
  • Jirka Matousek's lecture notes on metric embeddings give a general survey, see Chapter 4 for Bourgain's theorem and Sparsest Cut.
  • Chapter 15 of [Williamson Shmoys] talks about metric embeddings and cut problems.
  • David Shmoys's survey also discusses embedding techniques.
  • Luca Trevisan's course notes on Graph Partitioning, Expanders, and Spectral Methods.


• Lecture 8 (Sep 17, AG). Sparsest Cut: Spectral Partitioning and the Cheeger Bounds (handwritten notes)
  • Luca Trevisan's course notes on Graph Partitioning, Expanders, and Spectral Methods.
  • Course notes on Spectral Graph Theory from Lap Chi Lau and David Williamson.
    Lap Chi discusses the (surprising) effect of higher eigenvalues on spectral clustering (which uses level sets of $\lambda_2$ to cluster).



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)
• Trevisan's original paper.
• Soto's 0.62 approximation tightening up Trevisan's analysis


• 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)
  • Section 9.2 of the Williamson-Shmoys book.
  • The second half of these lecture notes from the 2008 version of the course.
  • We followed an arxiv note of Gupta and Tangwongsan simplifying the previous analysis of Arya, Garg, Khandekar, Meyerson, Munagala and Pandit.


• 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 notes by Ryan and Venkat on the PCP Theorem.
  • The Story of the PCP Theorem by Dana Moshkovitz.
  • Ran Raz's Parallel Repetition Theorem proves NP-hardness of Label Cover.
  • Johan Hastad's Some Optimal Inapproximability Results that introduced Fourier analytic techniques for hardness of approximation.
  • Trevisan, Sorkin, Sudan and Williamson's paper that automates the task of finding good gadgets for reductions.


• 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.)
  • Ryan O'Donnell's notes on the Lindeberg replacement method to prove central limit theorem.



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)
  • The Grotschel-Lovasz-Schrijver book for all your Ellipsoid needs.
  • See Chapter 7.1 of the Matousek and Gaertner book for a discussion on Ellipsoid.
  • The Yamnitsky-Levin paper on the Simplices Method.
  • Bartels' paper on the bit-complexity of the [YL82] paper.
  • Lecture notes on the classical "Ellipsoids" version of the Ellipsoid Algorithm from our 15-850 course, from a previous 15-859 course, and from Michel Goemans.


• 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.