Algorithms Seminar/Fall09
From ResearchWiki
(Difference between revisions)
m |
(→Schedule) |
||
| Line 27: | Line 27: | ||
| Sep 9 || Greedy algorithms: [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture03.pdf Set Cover, Makespan] || Parasaran | | Sep 9 || Greedy algorithms: [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture03.pdf Set Cover, Makespan] || Parasaran | ||
|- | |- | ||
| - | | Sep 16 || Dynamic Programming: [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture04.pdf Knapsack], [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture05.pdf Bin Packing]|| | + | | Sep 16 || Dynamic Programming: [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture04.pdf Knapsack], [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture05.pdf Bin Packing]|| Avishek |
|- | |- | ||
| Sep 23 || Local Search I: MAX CUT, Facility Location (part [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture07.pdf I], [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture08.pdf II])|| | | Sep 23 || Local Search I: MAX CUT, Facility Location (part [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture07.pdf I], [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture08.pdf II])|| | ||
Revision as of 20:50, 2 September 2009
Time: Wednesday 1:25-2:45pm (note the changed time)
Place: LCR (MEB 3147)
We will cover approximation algorithms this fall. more details later on...
Readings
- Approximation Algorithms Course @ Wisconsin
- Approximation Algorithms, Vijay Vazirani
Participants
- Suresh Venkatasubramanian, Assistant Professor, School of Computing
- Parasaran Raman, PhD Student, School of Computing
- John Moeller, PhD Student, School of Computing
- Raj Varma Kommaraju, MS Student, School of Computing
- Adam R. Teichert, MS Student, School of Computing
- Avishek Saha, PhD Student, School of Computing
- Seth Juarez, PhD Student, School of Computing
Schedule
| Date | Paper(s) | Presenter |
|---|---|---|
| Sep 2 | Basic methods: Vertex Cover and metric TSP, and Steiner Tree | Suresh |
| Sep 9 | Greedy algorithms: Set Cover, Makespan | Parasaran |
| Sep 16 | Dynamic Programming: Knapsack, Bin Packing | Avishek |
| Sep 23 | Local Search I: MAX CUT, Facility Location (part I, II) | |
| Sep 30 | Local Search II: MAX CUT, Facility Location (part I, II) . Also see these simplified notes | |
| Oct 7 | LP rounding: Congestion | |
| Oct 21 | Primal Dual I: Steiner Trees, Facility Location (part I, part II, part III) | |
| Oct 28 | Primal Dual II: Steiner Tree, Facility Location (part I, part II, part III) | |
| Nov 4 | Approximations via Tree Embeddings | |
| Nov 11 | Sparsest Cut and Metric Embeddings I | |
| Nov 18 | Sparsest Cut and Metric Embeddings II | John |
| Nov 25 | SDPs I: Basics and MAX CUT | |
| Dec 2 | SDPs II: Graph Coloring | |
| Dec 9 | MCMC |
