Event Type:

Number Theory Seminar

Date/Time:

Tuesday, June 6, 2017 - 16:00 to 17:00

Location:

Bexell 328

Guest Speaker:

Institution:

School of Electrical Engineering and Computer Science at OSU

Abstract:

Given a finite metric space (X, dX), consider the problem of finding a host metric space from within some class of “simple” metric spaces that (X, dX) can be embedded into while preserving pairwise distances as much as possible. This is a central problem in the algorithmic study of metric spaces, as naturally finding such a simpler metric can unlock a set of efficient algorithmic tools which may be less effective on more complex spaces.

Among alternatives, one of the most widely studied classes of simpler host metric spaces is the class of weighted trees, whose structure is well understood and readily allows one to apply tools such as dynamic programming. Furthermore, such embeddings have found natural applications, for example, in estimating the phylogenetic tree.

Closely related to finding embeddings into tree metrics of minimum distortion is the problem of finding tree spanners with minimum stretch, spanning trees that preserve pairwise distances as much as possible. As minimal distance preserving structures, tree spanners have found applications in distributed systems

In this talk, I will present approximation algorithms for finding low distortion embeddings into trees, and for finding minimum stretch tree spanners.

This is a joint work with Banjamin Raichel. Here is a link to the paper: http://web.engr.oregonstate.edu/~nayyeria/pubs/host-tree.pdf