Algorithms Reading Team -- Fall 2003

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
09/05/2003 15:00-16:00 CN 149 Organizational meeting.
09/19/2003 11:30-13:00 CN 149 R. Rajaraman Network information flow.
10/03/2003 11:30-13:00 CN 149 J. Aslam Sublinear computing.
10/10/2003 11:30-13:00 CN 149 X. Liu A. Srinivas et al.: Minimum energy disjoint path routing in wireless Ad-Hoc networks.
10/17/2003 11:30-13:00 CN 149 G. Lin J. Fakcharoenphol et al.: A tight bound on approximating arbitrary metrics by tree metrics.
10/24/2003 11:30-13:00 CN 149 R. Ye A. Carzaniga et al.: Forwarding in a content-based network.
10/31/2003 11:30-13:00 CN 149 Alex Russell (UConn) Elementary Tools for Quantum Computation: Fourier Transforms and Hidden Subgroups.
11/07/2003 11:30-13:00 CN 149 L. Jia J. Könemann et al.: A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees.
11/14/2003 11:30-13:00 CN 149 Y. Du Language trees and zipping; similarity metric.
11/26/2003 14:00-15:30 CN 247 Mayur Thakur (U. of Rochester) Broad-Brush Theorems for Determining Problem Complexity.
12/05/2003 11:30-13:00 CN 149 R. Sundaram J. Chuzhoy et al.: Asymmetric k-center is log^*n hard to approximate.

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

  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.

  3. Network Algorithms

  4. Minimum energy disjoint path routing in wireless Ad-Hoc networks. A. Srinivas and E. Modiano. Mobicom 2003.
  5. 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.
  6. Constant-time distributed dominating set approximation. F. Kuhn and R. Wattenhofer. PODC 2003.  [ps]
  7. Approximation Algorithms

  8. 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.
  9. 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.
  10. 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.
  11. 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.

  12. 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]
  13. Networks and Information Theory

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

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.