| Week # |
Date |
Topic |
Presenter |
Topic Reading / Associated Paper |
Assignment Link |
Due Date |
| 1 |
Feb. 6 |
-- |
-- |
-- |
tex, pdf
|
Wed. Feb 14 |
| Feb. 8 |
Online Makespan Minimization |
Bender |
Makespan Minimization via Posted Prices |
| 2 |
Feb. 13 |
Linear Programs |
Bender |
Wiki, Chap. 29 of
CLRS |
tex, pdf
|
Wed. Feb 21 |
| Feb. 15 |
Match-Making with Delays |
Bender |
A Primal-Dual Online Deterministic Algorithm for Matching with
Delays |
| 3 |
Feb. 20 |
Metric Embedding |
Bender |
Lecture
Notes from Anupam Gupta (basically one of my favorite people), a nicely presented proof of analysis
|
tex, pdf
|
Wed. Feb. 28 |
| Feb. 22 |
A return to Online Matching |
Bender |
Randomized online algorithms for minimum metric
bipartite matching |
| 4 |
Feb. 27 |
P vs NP |
Bender |
Wiki, Chap. 34
sections 1 - 3 of
CLRS |
tex, pdf
|
Wed. Mar. 6 |
| Mar. 1 |
- Pricing Deterministic Algorithms on the Line for Min-Metric Matching
- Applications of Quantum Theory to Algorithmic Game Theory
|
- Thor G. and Gerry L.
- Emerson B. and Meredith G.
|
- Online Weighted
Matching
- Chapter 10 of Computational Complexity, A
handy-hand-out
|
| 5 |
Mar. 6 |
NP-Hardness, NP-Completeness |
Bender |
Wiki, Chap. 34
sections 4-6 of
CLRS |
tex, pdf |
Fri. Mar. 15 |
| Mar. 8 |
Interactive Proofs, PCP Theorem |
Bender
|
Chapter 8 of Computational Complexity, Wiki on IP, Wiki on PCP |
| 6 |
Mar. 13 |
-- |
Bender |
-- |
-- |
-- |
| Mar. 15 |
-- |
- Aum D. and David I.
- Hakan E. and Alexandra A.
|
-- |
| 7 |
Mar. 20 |
-- |
-- |
-- |
-- |
-- |
| Mar. 22 |
-- |
- Alex B. and Liam M.
- Lili N. and Alfie N.
|
-- |
| 8 |
Mar. 27 |
Spring Break |
| Mar. 29 |
| 9 |
Apr. 2 |
-- |
-- |
-- |
-- |
-- |
| Apr. 4 |
-- |
-- |
-- |
| 10 |
Apr. 9 |
-- |
-- |
-- |
-- |
-- |
| Apr. 11 |
-- |
-- |
-- |
| 11 |
Apr. 16 |
-- |
-- |
-- |
-- |
-- |
| Apr. 18 |
-- |
-- |
-- |
| 12 |
Apr. 23 |
-- |
-- |
-- |
-- |
-- |
| Apr. 25 |
-- |
-- |
-- |
| 13 |
Apr. 30 |
CLAS |
| May 2 |
| 14 |
May 7 |
-- |
-- |
-- |
-- |
-- |
| May 9 |
-- |
-- |
-- |
Email me the .pdf and any other necessary files. All assignments due 10PM ET on the given due date.