Schedule

Tentative; subject to change.

Introduction

4/1
Introduction: Three motivating examples (caching, linear programming, clustering). Instance optimality.
Lecture notes
Intro slides
Supplemental reading:

Instance optimality

4/3
Instance optimality: Instance optimality in computational geometry.
Lecture notes
Textbook: Chapter 3
Supplemental reading:

Resource augmentation

4/8
Resource augmentation: Online paging. Resource augmentation. Loose competitiveness.
Lecture notes
Textbook: Chapter 4
Supplemental reading:
  • General reference for online paging and online algorithms more generally: book by Borodin and El-Yaniv.

Parameterized algorithms and analysis

4/10
Parameterized paging: Parameterized analysis of online paging. Parameterizing page sequences by their locality. Optimal page fault bounds for LRU. Rigorously separating LRU and FIFO.
Lecture notes
Supplemental reading:
  • Related video (from the 2011 workshop on BWCA): Susanne Albers on locality of reference in competitive analysis.
HW1 out due 4/24
4/15
Parameterized algorithms: NP-hard problems and what to do about them. The knapsack problem and parameterized approximation bounds. Parameterized algorithms and a polynomial-size kernel for the vertex cover problem. Color-coding and the longest path problem.
Lecture notes
Textbook: Chapter 2
Supplemental reading:
  • Parameterized algorithms is a huge field: here is a recent textbook on the topic.

Perturbation stability

4/17
Perturbation-stable clustering
Lecture notes
Textbook: Chapter 5
Supplemental reading:
4/22
Perturbation-stable minimum cuts: When are linear programming relaxations exact? Case study: perturbation-stable instances of the minimum multiway cut problem.
Lecture notes
Textbook: Chapter 5
Supplemental reading:
4/24
Perturbation-stable maximum cuts: Exact recovery in perturbation-stable instances of the maximum cut problem. Metric embeddings and Bourgain’s Theorem. Improvements via semidefinite programming.
Lecture notes
Textbook: Chapter 5
Supplemental reading:
HW1 due due at 11:59pm
HW2 out due 5/8
4/29
No class

Spectral algorithms for planted bisection and clique

5/1
Spectral algorithms for planted bisection: Random graphs. Planted models. A spectral algorithm for the planted bisection problem.
Lecture notes
Textbook: Chapter 8
Supplemental reading:
  • Our presentation is loosely based on lecture notes of Spielman, here and here.
5/6
Spectral algorithms for planted clique: A little matrix perturbation theory. A spectral algorithm for the planted clique problem.
Lecture notes
Textbook: Chapter 8
Supplemental reading:

Semi-random models and semidefinite programming

5/8
Semi-random models and semidefinite programming: Case study: minimum bisection. SDP duality.
Lecture notes
Textbook: Chapter 9
Supplemental reading:
HW2 due due at 11:59pm
HW3 out due 5/22
5/13
Semi-random models and semidefinite programming: Finish bisection. Second case study: maximum clique.
Lecture notes
Textbook: Chapter 9
Supplemental reading:

Nonnegative matrix factorization

5/15
Nonnegative matrix factorization: Exact recovery: topic models and nonnegative matrix factorization.
Lecture notes
Textbook: Chapter 20
Supplemental reading:

Random order models

5/20
Random ordering problems: Secretary problems. Case study: online facility location.
Lecture notes
Textbook: Chapter 11
Supplemental reading:

Smoothed analysis

5/22
Smoothed local search: Smoothed analysis of local search heuristics. Case study: the 2OPT local search heuristic for TSP in the plane.
Lecture notes
Textbook: Chapter 13
Supplemental reading:
HW3 due due at 11:59pm
HW4 out due 6/5
5/27
Pseudopoly = Smoothed Poly: For binary optimization problems, polynomial smoothed complexity <=> (Las Vegas randomized) pseudopolynomial worst-case complexity.
Lecture notes
Supplemental reading:

Algorithms with predictions

5/29
Algorithms with predictions
Lecture notes
Textbook: Chapter 30
Supplemental reading:

Final project presentations

6/3
Final project presentations
6/5
HW4 due due at 11:59pm