The course meets Fridays, 1:30-3:30, in Rhodes 261.
This course will read recent papers in combinatorial optimization, with a focus on approximation algorithms. Each student will be responsible for presenting 1-2 papers during the term. All attendees are responsible for reading the paper for the week.
| Jan 25 | Course organization. | |
|---|---|---|
| Feb 1 | No class. | |
| Feb 8 | David Shmoys | An, Kleinberg, and Shmoys, Improving Christofides' Algorithm for the s-t Path TSP |
| Feb 15 | Eoin and Ashwinkumar | Li and Svensson, Approximating k-Median via Pseudo-Approximation |
| Feb 22 | Daniel and Jake | Nagarajan, Schieber, and Shachnai, The Euclidean k-Supplier Problem | Mar 1 | James and Alice | Sebő, Eight-Fifth Approximation for TSP Paths |
| Mar 8 | No class. | |
| Mar 15 | No class. | |
| Mar 22 | No class. | |
| Mar 29 | Anna and Vasilis | Mömke and Svensson, Approximating Graphic TSP by Matchings |
| Apr 5 | No class. | |
| Apr 12 | Chaoxu and Nima | Rothvoß, A Simpler Proof for O(Congestion + Dilation) Packet Routing |
| Apr 19 | Pat and Soroush | Rothvoß, Approximating Bin Packing within O(log OPT loglog OPT) Bins |
| Apr 26 | Lior and Jerry | Buchbinder, Feldman, Naor, and Schwartz, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization |
| May 3 | Hedyeh, Pooya, and Rad | Vishnoi, A Permanent Approach to the Traveling Salesman Problem |
| May 7 | Alex, Yang, and Chen | Lovett and Meka, Constructive Discrepancy Minimization by Walking on the Edges |