[Lowerbounds, Upperbounds]

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.

SPEAKER: Ho-Leung Chan
TIME: Wednesday 12-1pm, January 24, 2007
PLACE: NSH 1507
TITLE: Energy efficient job scheduling

ABSTRACT:

Energy efficiency is an important concern for mobile devices. A major method to reduce energy usage is to adjust the speed of processor, because the processor consumes less energy when running at slower speed. Yet, the processor needs to provide certain performance guarantee, say meeting the deadlines of all incoming jobs or maximizing the total throughput. In this talk, we will discuss algorithms to determine the processor speed, which provide the required performance and are also competitive on energy usage

SPEAKER: Ryan Williams
TIME: Wednesday 12-1pm, January 17, 2007
PLACE: NSH 1507
TITLE: Matrix-Vector Multiplication in Subquadratic Time (Some Preprocessing Required)

ABSTRACT:
We show that any n by n matrix A over any finite semiring can be preprocessed in O(n^{2+eps}) time, such that all subsequent vector multiplications with A can be performed in O(n^2/(eps log n)^2) time, for all eps > 0. The approach is combinatorial and can be implemented on a pointer machine or a (log n)-word RAM. Some applications are described.

A bit shorter version of this talk was presented last week, at SODA in New Orleans.