Approximation
Algorithms on Metric Spaces and Graphs
By

Dr.
Hubert Chan

Postdoctoral
Researcher, Max Planck Institute for Informatics
in Germany

Date:
Oct 3, 2008 (Friday) 
Time:
2:00p.m.  3:00 p.m. 
Venue:
Rm. 1027, Ho Sin Hang Engineering Building,
CUHK 
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 wellknown NPhard problem. However,
for perfect graphs, this quantity coincides with the
Lovasz Theta function, which can be wellapproximated
via an SDP. We use Arora and Kale's framework for
SDP to design a primaldual 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 webgraph models. He is
currently working as a postdoc at MaxPlanckInstitut
fuer Informatik in Germany.
