About ART

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.

• Each team member is supposed to read at least the beginning sections (introduction, problem setup, main results) before the meeting, so that the minimum amout of time will be spent on definitions, notations and other background knowledge.
• The presenter is supposed to read through the main part of the paper, so that s/he can quickly review the main idea / logic / technique of the works, answer some non-trivial questions and initiate and lead the discussion.
• After each meeting, the presenter shall write a memo summarizing the open problems either mentioned in the paper or raised by the team members and publish them on the mailing list (one paragraph in text format would be good).

Schedule

Topics

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