SPEAKER: Hubert Chan.

TIME: Wednesday 12-1pm, January 31, 2007.

PLACE: NSH 1507

TITLE:  Approximating TSP for Bounded Dimensional Metric Spaces

ABSTRACT:

While TSP is NP-hard to approximate within a factor better than 174/173 for 
general metrics, there exist efficient PTAS's for low dimensional Euclidean 
spaces.  However, the notion of Euclidean dimension does not apply to general 
metrics.  The idea of doubling dimension generalizes that of Euclidean 
dimension, and intuitively bounds the local growth rate everywhere in the 
metric.   Recently, a quasi-PTAS was given to approximate TSP for metrics 
with bounded doubling dimension.   Our work follows this direction of 
research, and explores a notion of dimension that captures the global growth 
rate of a metric.  Although the notion of global dimension strictly 
generalizes that of doubling dimension, we show that for metrics with bounded 
global dimension, TSP can still be approximated within a factor arbitrarily 
close to 1 in sub-exponential time.