Speaker: Hubert Chan

Time: Wednesday 12-1pm

Location: NSH 3305

Title: Sparse Spanners for Doubling Metrics

Abstract:

Graph spanners have applications in communication networks,
distributed computing and computational geometry.  We motivate our
problem by considering the following application in wireless networks.
Suppose we have a set of nodes representing wireless access points.
Data packets can be sent from one node to another directly if the two
nodes are directly connected via a dedicated frequency.  Otherwise,
data packets have to travel through intermediate nodes from the source
to the destination.  Every pair of nodes (x,y) has some distance
d(x,y), which represents the time to send a data packet between the
nodes x and y if there is a direct connection between them.  The goal
is to construct a network by assigning a small number of dedicated
frequencies for directly connected pairs (which form a sparse spanner)
such that for every pair of nodes (u,v), the time to send a data
packet between them is at most some small multiplicative factor
(typically less than 1.5) of d(u,v).

We show that if the distance function obeys some bounded growth
property (namely, induces a doubling metric), then it is possible to
construct such a network with a linear number of direct connections.
The bounded growth property is general enough to include many common
distance functions, such as constant dimensional Euclidean distances.

We also show that the network has additional nice properties, such as
each node having a constant number of connections.  Moreover, if we
allow the number of connections to be nearly linear O(n log*n), then
for every pair of nodes, there is a short path between them that uses
only a constant number of intermediate nodes.  This is useful when
congestion and latency are taken into account.

This is joint work with Anupam Gupta.

** This is a speaking requirement talk.