Reading material
|
Date
|
Tentative Topics
| Reading material
| Scribe
|
Dec 31, Jan 7, 10
|
Linear Programming and Duality. Path formualtion of s-t flow
|
| Lec2
Lec3
|
Jan 14
|
Online learning and multiplicative weight updates
| Slides from Avrim Blum
| Lec4
Lec5
|
Jan 17
|
Applications of MW: solving LPs, multicommodity flows
| Computing multicommodity flows
Survey by Arora et.al.
| Lec6
|
| Jan 24, 28, 31 |
Setcover, fractional setcover, covering LPs
|
Fractional setcover
|
Lec7
Lec8
Lec9
|
| Feb 11 |
Width dependent algorithm for simultaneous convex fn minimzation
|
|
Lec 10 |
Feb 14, 18
|
max flow using electrical flows
| Lecture 12,17,18 from Williamson's course
| Lec11
Lec12
|
Feb 21, 23, 25, 28
|
Matchings via Polynomial Identity Testing, APSP via matrix multiplication
|
Lecture 4,9 from Anupam Gupta's Advanced Algorithms course
| Lec13, Lec14, Lec15, Lec16
|
Mar 11, 14, April 1, 4, 11
|
Streaming Algorithms
|
Amit Chakrabarti's course notes
| Lec17
Lec18
Lec20
Lec21
|
Apr 12, 15, 18
|
Online Algorithms, Paging
|
Albers mini course
| Lec22
Lec23
|
Apr 22, 25
|
Online Primal-Dual, k-server
|
Naor's slides 1, 2, 3
Online Packing
|
|
|
|