Algorithms and Complexity Seminar
Thursday, May 10, 2007, 4-5:15pm in 32-G575.
Approximation algorithms for doubling dimensional metric spaces
Kyomin Jung (MIT)
The problem of computing marginal probability or mode of distribution
in Markov
Random Fields(MRF) is central in statistical inference. These problems
are hard
in general, however it becomes easy when the underlying graph G of the
MRF is a
tree or locally tree-like, based on essentially dynamic programming
approach.
Many of existing inference algorithms including Belief propagation and
Max-product algorithms are based on these properties. Our problem of
interest
is identifying more general class of graphs that yield Polynomial Time
Approximation Scheme(PTAS) for these problems. First we obtain
randomized PTAS
for these problems when G has o(sqrt(log log n)) doubling dimension.
Then we
provide a derandomization to obtain deterministic PTAS under the same
condition.
This is based on joint work with Devavrat Shah.
Host: Madhu Sudan
(The Algorithms
and Complexity Seminar series talks are usually held Thursdays from
4-5:15pm in 32-G575.)