Algorithms on Metric Spaces and Graphs
Researcher, Max Planck Institute for Informatics
Oct 3, 2008 (Friday)
2:00p.m. - 3:00 p.m.
Rm. 1027, Ho Sin Hang Engineering Building,
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
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.
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.