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