Algorithms Reading Team

About ART

The Algorithms Reading Team focuses on algorithm-related problems and their applications in various fields. The topics include algorithmic problems encountered in or abstracted from concrete problems in theory, networking, databases, information retrieval and systems. New topics are always welcome.

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.


Schedule

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

Topics

The following is a list of papers/presentations/focused topics suggested by Prof. Aslam, Prof. Noubir, Prof. Rajaraman and Prof. Sundaram.

    Information Retrieval

  1. Performance guarantees for hierarchical clustering. S. Dasgupta. Computational Learning Theory (COLT), 2002.  [ps]

    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).


Members

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

Activities of ART in Spring 2003 can be found here.
Activities of ART in Fall 2003 can be found here.