The objective of the Algorithms Reading Team is to read and understand the most recent works in discrete algorithms, and most importantly (and hopefully) to identify potential topics to work on.
The general format of the meetings will be whiteboard presentations followed by interactive open-problem discussions.
|Date||Time||Location||Presenter||Paper / Topic|
|01/23/2004||11:30-13:00||CN 149||H. Wu||S. Dasgupta: Performance guarantees for hierarchical clustering.|
|02/11/2004||12:00-13:30||CN 149||Kofi Laing (Tufts)||Name Independent Compact Routing|
|02/17/2004||11:00-12:30||CN 149||J. Chen||A. Gupta et al.: Boosted sampling: approximation algorithms for stochastic optimization.|
|02/24/2004||11:00-12:30||CN 149||Robert D. Kleinberg (MIT)||R. Kleinberg et al.: The Value of Knowing a Demand Curve: Bounds on Regret for On-Line Posted-Price Auctions [abstract]|
|03/23/2004||11:00-12:30||CN 149||F. Zhu||S. Shakkottai et al.: Unreliable sensor grids: coverage, connectivity and diameter (IEEE INFOCOM 2003)|
|03/30/2004||11:00-12:30||CN 149||V. Pavlu||J. Aslam et al.: A Unified Model for Metaseach, Pooling and System Evaluation
Y. Freund et al.: A decision theoretic generalization of on-line learning and application to boosting
|04/06/2004||11:00-12:30||CN 149||R. Rajaraman||F. Kuhn et al.: Constant-time distributed dominating set approximation (PODC 2003)|
|04/13/2004||11:00-12:30||CN 149||D. G. Antonova||S. Eidenbenz et al.: Equilibria in Topology Control Games for Ad Hoc Networks|
|04/20/2004||11:00-12:30||CN 149||Michael A. Bender (SUNY Stony Brook & MIT)||Cache-Oblivious Searching|
There have been a ton of papers on clustering techniques, but this is one of the few that gives an approximation algorithm with performance guarantees. Highly algorithmic and very nice, in my opinion. A nice application useful in learning, information retrieval, etc.
Sanjoy has also posted PowerPoint slides. There is also a follow-up paper by Greg Plaxton in STOC 2003 (Approximation algorithms for hierarchical location problems).
|Javed A. Aslam||Agnes Chan||Guevara Noubir||Rajmohan Rajaraman||Ravi Sundaram|
|Daria G. Antonova||Jiangzhuo Chen||Yang Du||Lujun Jia||Guolong Lin|
|Xin Liu||Huanmei Wu||Tian Xia|