Spring 2006 CSE642 Algorithms Seminar

Locations and Hours:

Friday 11:00-12:30 @ Computer Science Lounge (CS Building 1211).

Course Description:

This reading group provides a meeting place for Stony Brook faculty, postdocs, and students interested in the analysis of algorithms. We meet once a week, with one of three different missions:

  • Paper presentations -- This is fairly informal, with one person (i.e. student) responsible each time for leading the discussions. Nobody will have to lead for more than one paper per semester.
  • Open Problem Bull Sessions -- where we pose and attack accessible research problems. A good time is had by all.
  • Road Trips -- to the special computational geometry or theory days at NYU, Columbia, and the like.

You can get one credit for participating by simply registering for CSE 642. You are also welcome to come without registering. 

We have a mailing list. Please email me (Jie Gao) if you want to be added to the list.

Schedules:

1/27: Zhenghao Zhang will talk about his research and interesting algorithm problems.

Title: Optimization Problems in Wireless Communications

Abstract: In this talk I will discuss a series of optimization problems related to wireless communications recently studied by us in two ongoing research projects. The first project is about applying Multiple Packet Transmission (MPT) technique to Wireless LANs, where MPT means that with two antennas, the sender can send two messages to two users at the same time. The problems of optimally utilizing the MPT technique can be formalized as a series of matching problems in a graph. The simplest problem can be formalized as finding a maximum matching and I will first describe an interesting newly discovered algorithm that finds an approximation of the maximum matching in linear time. Then I will discuss some open research problem related to providing Quality of Service (QoS). These problems can also be formalized as matching problems but with additional constraints. I will describe an interesting solution to a special case of the problem and then describe our attempts to solving the more general cases. After that I will move on to the problems in the next project and I will focus on a very interesting and still open problem which is to permute points on a plane such that the distances between all pairs of points satisfy some constraints.

2/3: Open problem session led by Zhenghao zhang.

1.      Colored matching problem.

2.      Permutation code problem.

2/10: Paper presentation by Amitabh Basu.

Title: Spanners and emulators with sublinear distance errors

Authors: Mikkel Thorup and Uri Zwick

Abstract: Let k \geq 2 be an integer. We show that any undirected and unweighted graph G = (V, E) on n vertices has a subgraph G' = (V, E') with O(kn^{1+1/k}) edges such that for any two vertices u, v \in V, if d_G(u, v) = d, then d_G'(u, v) = d+O(d^{1-1/(k-1)}). Furthermore, we show that such subgraphs can be constructed in O(mn^{1/k}) time, where m and n are the number of edges and vertices in the original graph. We also show that it is possible to construct a weighted graph G* = (V, E*) with O(kn^{1+1/(2^k-1)}) edges such that for every u, v \in V, if d_G(u, v) = d, then d = d_G*(u, v) = d + O(d^{1-1/(k-1)}). These are the first such results with additive error terms of the form o(d), i.e., additive error terms that are sublinear in the distance being approximated.

Note: It appeared in ACM-SIAM SODA’06.

2/17: Another spanner paper with the same basic randomized hierarchy.

Title: Approximate distance oracles

Authors: Mikkel Thorup and Uri Zwick

Abstract: Let G=(V,E) be an undirected weighted graph with |V|=n and |E|=m. Let k\ge 1 be an integer. We show that G=(V,E) can be preprocessed in O(kmn^{1/k}) expected time, constructing a data structure of size O(kn^{1+1/k}), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k-1, i.e., the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k-1. We show that a 1963 girth conjecture of Erd{\H{o}}s, implies that &ohgr(n^{1+1/k}) space is needed in the worst case for any real stretch strictly smaller than 2k+1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name ``oracle''. Previously, data structures that used only O(n^{1+1/k}) space had a query time of &ohgr(n^{1/k}) and a slightly larger, non-optimal, stretch. Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.

Appeared in STOC’01.

2/21: Open problem session related to skip graphs.

3/3: Paper presentation by Yonatan Fogel.

Title: A Simplified and Dynamic Unified Structure, by Mihai Bădoiu and Erik D. Demaine

3/10: Open problem session led by Joe Mitchell.

3/17: Open problem session on greedy routing with virtual coordinates.

3/24: Backoff scheme presented by Michael Bender.

3/31: Paper presentation by Michael Bautin.

Analyzing BitTorrent and Related Peer-to-Peer Networks, David Arthur and Rina Panigrahy, ACM-SIAM SODA’06.

4/7: TBD.

4/14: Spring break.

4/21: TBD.

4/28: TBD.

5/5: TBD.

Reading list: (you can choose a paper to present)

·        Spanners and emulators with sublinear distance errors, by Mikkel Thorup and Uri Zwick, ACM-SIAM SODA’06.

·        Skip graphs, by James Aspnes and Gauri Shah, ACM-SIAM SODA’03, January 2003, pp. 384–393.

·        Analyzing BitTorrent and Related Peer-to-Peer Networks, David Arthur and Rina Panigrahy, ACM-SIAM SODA’06.

·        A General Approach for Incremental Approximation and Hierarchical Clustering, Guolong Lin and Chandrashekhar Nagarajan and Rajmohan Rajaraman and David P. Williamson, ACM-SIAM SODA’06.

Last updated: 01/25/06