CSAIL Event Calendar: Previous Series
Approximation algorithms for doubling dimensional metric spaces
Speaker: Kyomin Jung , MIT
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/kyomin-abs.html
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.