Algorithms Reading Team -- Spring 2003

The Algorithms Reading Team will focus on discrete algorithms and their application on network problems. The topics include approximation algorithm analysis for hard problems, data structure analysis in information retrieval, network scheduling. 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. 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.

Date Time Location Presenter Paper / Topic
04/18/2003 15:30-17:00 Egan 306 J. Chen E. Halperin et al.: Integrality ratio for group steiner trees and directed steiner trees.
05/16/2003 15:30-17:00 Egan 406 X. Ma G. Blelloch et al.: Space-efficient finger search on degree-balanced search trees.
05/30/2003 15:30-17:00 Egan 306 L. Jia W. Aiello et al.: Dynamic routing on networks with fixed-size buffers.
06/23/2003 15:00-17:00 Egan 206 G. Lin A. Goel et al.: Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk.
06/30/2003 15:00-17:00 Egan 206 Y. Du R. Fagin et al.: Comparing top K lists.

The following is a list of full references.  [BibTeX]  [pdf]  They are from Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03) by default, so they are all available online. For example, the scanned version can be downloaded from with a CCIS machine.