[Colloquium] Guest Speaker Announcement

[Ponda Barnes]

Guest Speaker
 
Presented by: Toyota Technological Institute at Chicago
 
Speaker: Hubert Chan
Speaker's home page: http://www.cs.uwaterloo.ca/~hy3chan 
 
Date: Tuesday, May 08, 2007
Time: 12:00 
Location: TTI-C Conference room
 
 
Title: Notions of Metric Dimension
 
Abstract:
 
The study of finite metrics is an important area of research, because of its
wide applications to many different problems.  Hence, it is desirable to
know what metrics admit better algorithms.  Many NP-hard problems become
more tractable for low-dimensional Euclidean metrics.
However, the notion of Euclidean dimension cannot be applied to general
metrics.  Clearly, a better notion of dimension should be used to
characterize the complexity of a general metric space.
 
One such notion is the doubling dimension, which is popular among the theory
community.  Many efficient algorithms for problems on low-dimensional
Euclidean space have counterparts for metrics with low
doubling dimension.  Sparse spanners are well studied for Euclidean
metrics and we extend the framework to doubling metrics.  For instance, we
construct linear sized (1 + \eps)-spanners for doubling metrics.
 
Observe that doubling dimension imposes a restriction on the local growth
rate everywhere in a metric.  Therefore, an otherwise simple metric with a
small locally complex region would have high doubling dimension.  We
investigate a new notion of metric dimension that captures the global
behavior of a metric.  For metrics with low global dimension, one would
expect better guarantees for problems whose objectives depend globally on
the input metrics.  Indeed, for the Traveling Salesman Problem on such
metrics, we give a sub-exponential time algorithm with approximation ratio
arbitrarily close to 1.
 
If you have any questions or would like to meet the speaker, please contact
Ponda Barnes at pondabarnes at tti-c.org
For future TTI-C talks and events please go to
http://ttic.uchicago.edu/cal/month.php
 
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070508/351a0543/attachment.html