Schedule
Tentative; subject to change.
Introduction
- 4/1
- Introduction: Three motivating examples (caching, linear programming, clustering). Instance optimality.
- Lecture notes
- Intro slides
- Supplemental reading:
- Fagin/Lotem/Naor, Optimal aggregation algorithms for middleware, JCSS ‘03.
- Lecture notes
Instance optimality
- 4/3
- Instance optimality: Instance optimality in computational geometry.
- Lecture notes
- Textbook: Chapter 3
- Supplemental reading:
- Afshani/Barbay/Chan, Instance-optimal geometric algorithms, FOCS ‘09.
- Lecture notes
Resource augmentation
- 4/8
- Resource augmentation: Online paging. Resource augmentation. Loose competitiveness.
- Lecture notes
- Textbook: Chapter 4
- Supplemental reading:
- Sleator/Tarjan, Amortized efficiency of list update and paging rules, CACM ‘85.
- Young, On-Line File Caching, SODA ‘98/Algorithmica ‘02.
- General reference for online paging and online algorithms more generally: book by Borodin and El-Yaniv.
- Lecture notes
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:
- Albers/Favrholdt/Giel, On Paging with Locality of Reference, STOC ‘02/JCSS ‘05.
- Related video (from the 2011 workshop on BWCA): Susanne Albers on locality of reference in competitive analysis.
- HW1 out due 4/24
- Lecture notes
- 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.
- Lecture notes
Perturbation stability
- 4/17
- Perturbation-stable clustering
- Lecture notes
- Textbook: Chapter 5
- Supplemental reading:
- The main result from today’s lecture is from Metric Perturbation Resilience. (Makarychev/Makarychev, 2016).
- The mentioned hardness result is from k-center Clustering under Perturbation Resilience. (Balcan/Haghtalab/White, 2016)
- For a survey of this area, see Center Based Clustering: A Foundational Perspective. (Awasthi/Balcan, 2014)
- Lecture notes
- 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:
- Makarychev/Makarychev/Vijayaraghavan, Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut, SODA ‘14.
- Lecture notes from a follow-up lecture
- Lecture notes
Spectral algorithms for planted bisection and clique
- 4/24
- Spectral algorithms for planted bisection: Random graphs. Planted models. A spectral algorithm for the planted bisection problem.
- Lecture notes
- Textbook: Chapter 8
- Supplemental reading:
- The planted bisection model is from Graph bisection algorithms with good average case behavior (Bui/Chaudhuri/Leighton/Siper, 1987).
- The matrix perturbation approach is from Spectral Partitioning of Random Graphs (McSherry, 2001).
- HW1 due due at 11:59pm
- HW2 out due 5/8
- Lecture notes
- 4/29
- No class
- 5/1
- 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:
- The spectral algorithm for planted clique is from Finding a large hidden clique in a random graph (Alon/Krivelevich/Sudakov, 1998).
- Project progress report due at 11:59pm
- Lecture notes
Semi-random models and semidefinite programming
- 5/6
- Semi-random models and semidefinite programming: Case study: minimum bisection. SDP duality.
- Lecture notes
- Textbook: Chapter 9
- Supplemental reading:
- Heuristics for Semirandom Graph Problems (Feige/Kilian, 2001)
- Lecture notes on SDP duality (Gupta, 2011)
- Lecture notes
- 5/8
- Semi-random models and semidefinite programming: Finish bisection. Second case study: maximum clique.
- Lecture notes
- Textbook: Chapter 9
- Supplemental reading:
- Finding and certifying a large hidden clique in a semi-random graph (Feige/Krauthgamer, 2000)
- HW2 due due at 11:59pm
- HW3 out due 5/22
- Lecture notes
Nonnegative matrix factorization
- 5/13
- Nonnegative matrix factorization: Exact recovery: topic models and nonnegative matrix factorization.
- Lecture notes
- Textbook: Chapter 20
- Supplemental reading:
- Computing a Nonnegative Matrix Factorization – Provably (Arora/Ge/Kannan/Moitra, 2012)
- A Practical Algorithm for Topic Modeling with Provable Guarantees (Arora/Ge/Halpern/Mimno/Moitra/Sontag/Wu/Zhu, 2013)
- Lecture notes
Random order models
- 5/15
- Random ordering problems: Secretary problems. Case study: online facility location.
- Lecture notes
- Textbook: Chapter 11
- Supplemental reading:
- Online Facility Location (Meyerson, 2011)
- Lecture notes
Smoothed analysis
- 5/20
- 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:
- Englert/Roeglin/Voecking, Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP, SODA ‘07 and Algorithmica.
- Lecture notes
- 5/22
- Pseudopoly = Smoothed Poly: For binary optimization problems, polynomial smoothed complexity <=> (Las Vegas randomized) pseudopolynomial worst-case complexity.
- Lecture notes
- Supplemental reading:
- Beier/Voecking, Typical Properties of Winners and Losers in Discrete Optimization, STOC ‘04/SICOMP ‘06.
- HW3 due due at 11:59pm
- HW4 out due 6/5
- Lecture notes
Automated algorithm configuration
- 5/27
- Automated algorithm configuration
- Lecture notes
- Textbook: Chapter 29
- Supplemental reading:
- Gupta/Roughgarden, A PAC Approach to Application-Specific Algorithm Selection, ITCS ‘16.
- Lecture notes
Algorithms with predictions
- 5/29
- Algorithms with predictions
- Lecture notes
- Textbook: Chapter 30
- Supplemental reading:
- Kumar/Purohit/Svitkina, Improving online algorithms via ML predictions, NeurIPS ‘18.
- Lecture notes
Final project presentations
- 6/3
- Final project presentations
- 6/5
- HW4 due due at 11:59pm
- 6/11
- Project final report due at 11:59pm