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

2. Language trees and zipping. D. Benedetto, E. Caglioti, and V. Loretto.  [pdf]
   The similarity metric. M. Li, X. Chen, X. Li, B. Ma, and P. Vitanyi.  [pdf]

   Both of these papers propose a methodology for computing the similarity of "objects" (text, music, etc.) based on Information Theory and/or Kolmogorov Complexity. In each case, they apply their methodology, along with a relatively well known heuristic for hierarchical clustering, to automatically compute "language trees," i.e., a hierarchical categorization of human languages. In each case, the results obtained closely mirror groupings produced by linguists.

Network Algorithms

3. Minimum energy disjoint path routing in wireless Ad-Hoc networks. A. Srinivas and E. Modiano. Mobicom 2003.
4. Forwarding in a content-based network. A. Carzaniga and A. Wolf. SIGCOMM 2003.  [pdf]
   A paper on content-based networks, in which nodes perform routing on the basis of the content of the messages. Appears to be a first paper in the area, and hopefully, offers scope for further research.
5. Constant-time distributed dominating set approximation. F. Kuhn and R. Wattenhofer. PODC 2003.  [ps]

Approximation Algorithms

6. A tight bound on approximating arbitrary metrics by tree metrics. J. Fakcharoenphol, S. Rao and K. Talwar. STOC 2003.  [ps]
   This could be presented together with a discussion of Bartal's earlier much-cited paper on the same topic (On Approximating Arbitrary Metrics by Tree Metrics); a topic that has found numerous applications in approximation algorithms.
7. Asymmetric k-center is log^*n hard to approximate. J. Chuzhoy, S. Guha, E. Halperin, S. Khanna, G. Kortsarz, R. Krauthgamer and J. Naor.   [ps]
   This is one of a set of results for which people have matching upper and lower bounds and there may be a general methodology here.
8. A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. J. Könemann and R. Ravi. STOC 2000.  [ps]
   Uses Lagrangian methods, has a number of interesting ideas.

Sublinear Computing

That is, what can you hope to compute and/or approximate without even looking at all the data. Bernard Chazelle is giving a plenary talk on the subject at the upcoming SODA, and Ronnit Rubinfeld gave a very interesting talk (Powerpoint slides) on the subject recently.
9. Spot-checkers. F. Ergun, S. Kannan, S. R. Kumar, R. Rubinfeld and M. Vishwanthan. JCSS 60, 717-751 (2000). Preliminary abstract appears in in Proc. 30th ACM Symposium on Theory of Computing, 1998.  [ps]

Networks and Information Theory

10. Polynomial time algorithms for network information flow. P. Sanders, S. Egner, and L. Tolhuizen. SPAA 2003.  [pdf]
    This appears to be a nice problem related to both network flows and coding theory.

Members