Abstract :

The study of finite metrics is an important area of research, because of its wide applications in the design of approximation algorithms. A fundamental question in metric embeddings is how well a given metric can be represented by a Euclidean metric - this representation is also known as an embedding. The quality of an embedding can be measured by two quantities: (1) the distortion of an embedding measures how much the distances under the new representation differ from those of the original metric; (2) the target dimension is the number of dimensions in the new Euclidean metric representation. Ideally, one would want an embedding of both low distortion and low target dimension. We give a tradeoff between these two quantities.

Computing the maximum independent set number for a given graph is a well-known NP-hard problem. However, for perfect graphs, this quantity coincides with the Lovasz Theta function, which can be well-approximated via an SDP. We use Arora and Kale's framework for SDP to design a primal-dual algorithm to approximate the Lovasz Theta function. Under some range of the maximum independent set number, our algorithm for computing this quantity for perfect graphs is the fastest among known methods.

Biography:

Hubert Chan has completed his PhD in Computer Science at Carnegie Mellon University in 2007. His main research interests are approximation algorithms and metric embeddings. In his PhD thesis, he investigates notions of metric dimension and the design of algorithms whose performance adapts to the dimension of the given metric. His research topics also include graph algorithms, item pricing problems and web-graph models. He is currently working as a post-doc at Max-Planck-Institut fuer Informatik in Germany.