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.
See other events that are part of Algorithms and Complexity Series 2006/2007 |
