Algorithms Seminar/Fall09
From ResearchWiki
(Difference between revisions)
(→Schedule) |
|||
| Line 45: | Line 45: | ||
| Nov 4 || [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture22.pdf Approximations via Tree Embeddings]|| || Jags | | Nov 4 || [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture22.pdf Approximations via Tree Embeddings]|| || Jags | ||
|- | |- | ||
| - | | Nov 11 || [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/ | + | | Nov 11 || [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture25.pdf MCMC] || || Adam |
|- | |- | ||
| - | | Nov 18 || [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/ | + | | Nov 18 || [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture17.pdf Sparsest Cut and Metric Embeddings I]|| || John |
|- | |- | ||
| - | | Nov 25 || | + | | Nov 25 || [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture18.pdf Sparsest Cut and Metric Embeddings II] || || John |
|- | |- | ||
| - | | Dec 2 || SDPs | + | | Dec 2 ||SDPs I: [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture20.pdf Basics and MAX CUT]|| || Piyush |
|- | |- | ||
| - | | Dec 9 || | + | | Dec 9 || SDPs II: [http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture21.pdf Graph Coloring]|| || Seth |
|} | |} | ||
Revision as of 03:18, 31 October 2009
Time: Wednesday 1:25-2:45pm
Place: LCR (MEB 3147)
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
- Jiarong Jiang, PhD Student, School of Computing
- Piyush Rai, PhD Student, School of Computing
- Jagadeesh J, PhD Student, School of Computing
- Ruihong Huang, PhD Student, School of Computing
- Arvind Agarwal, PhD Student, School of Computing
Schedule
| Date | Paper(s) | Problems | Presenter |
|---|---|---|---|
| Sep 2 | Basic methods: Vertex Cover and metric TSP, and Steiner Tree | Suresh | |
| Sep 9 | Greedy algorithms: Set Cover, Makespan | Exercises | Parasaran |
| Sep 16 | Dynamic Programming: Knapsack, Bin Packing, Vazirani book Chap 9 | Avishek | |
| Sep 23 | Local Search I: MAX CUT, Facility Location (part I, II) | Ruihong | |
| Sep 30 | Local Search II: MAX CUT, Facility Location (part I, II) . Also see these simplified notes | Raj | |
| Oct 7 | LP rounding: Congestion (part or section 9.5.3) | Jiarong | |
| Oct 21 | Primal Dual I: Steiner Trees, Facility Location (part I, part II, part III) | Arvind | |
| Oct 28 | Primal Dual II: Steiner Tree, Facility Location (part I, part II, part III) | Suresh | |
| Nov 4 | Approximations via Tree Embeddings | Jags | |
| Nov 11 | MCMC | Adam | |
| Nov 18 | Sparsest Cut and Metric Embeddings I | John | |
| Nov 25 | Sparsest Cut and Metric Embeddings II | John | |
| Dec 2 | SDPs I: Basics and MAX CUT | Piyush | |
| Dec 9 | SDPs II: Graph Coloring | Seth |
