Rough schedule & presentation ideas:
Here is a rough schedule and some ideas for presentations. If you
have a general topic you're interested in and its not listed here,
come talk with me and we can figure out an appropriate paper.
Because of the class size, let's do the presentations in pairs:
e.g., one person could present and the other could prepare a
handout, or each partner could present half of the material. If
you'd rather do a project (e.g., some experiments or working on an
open problem and then a short (15 min) presentation on your
ideas and findings), come talk with me.
Presentations on approx topics could be done in the middle of the
course or at the end.
Schedule:
- Intro to apx and online: vertex cover, rent/buy, pursuer/evader
- Set cover, p-center: greedy and intro rand rounding.
- Max-SAT: conditional expectation and rand rounding.
- Routing (finish rand rounding), Chernoff bounds. A little about
Approx hardness.
- PTASs
- Computational biology problems
- Semi-definite Programming (1 or 2)
Then, some of the following in some order (these could be presentation
topics)
- random projection for proximity problems
- approximate counting problems
- balanced cuts / multicuts
- geometric TSP PTAS
- Primal-dual, k-MST and traveling deliveryman
- other facility location, k-median
- spanners and related subgraph/design problems
- other routing/scheduling
- more on approx hardness
Then Online Algs:
- MTS and paging
- navigation
- simple data structures
- k-server & work-function (1 or 2)
- online learning
- Bartal's metric approx & MTS (1 or 2)
Then, some of the following in some order (these could be presentation
topics)
- splay trees
- load balancing
- call control
- online financial algs (1 or 2)
- more on paging
- decision theory, game theory