Tata Institute of Fundamental Research
How Hard is it to Marry at Random?
Student Seminar
Speaker:
Girish Varma
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Friday, 23 Oct 2009 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods), are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample from the desired distribution. The quality of the sample improves as a function of the number of steps. We will use such a thing for generating a random perfect matching.
Reference :
Approximating the permanent M Jerrum, A Sinclair - SIAM journal on computing, 1989 - link.aip.org
How hard is it to marry at random? AZ Broder - Proceedings of the eighteenth annual ACM symposium …, 1986 - portal.acm.org
| Speaker: | Girish Varma School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Friday, 23 Oct 2009 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods), are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample from the desired distribution. The quality of the sample improves as a function of the number of steps. We will use such a thing for generating a random perfect matching.
Reference :
Approximating the permanent M Jerrum, A Sinclair - SIAM journal on computing, 1989 - link.aip.org
How hard is it to marry at random? AZ Broder - Proceedings of the eighteenth annual ACM symposium …, 1986 - portal.acm.org
Reference :
Approximating the permanent M Jerrum, A Sinclair - SIAM journal on computing, 1989 - link.aip.org
How hard is it to marry at random? AZ Broder - Proceedings of the eighteenth annual ACM symposium …, 1986 - portal.acm.org