Return to Colloquia & Seminar listing
Applications of Markov Chains to Combinatorics
Student-Run Discrete Math Seminar| Speaker: | David Sivakoff, UC Davis |
| Location: | 2112 MSB |
| Start time: | Thu, Jan 31 2008, 3:10PM |
Suppose S is a large set of combinatorial structures, and \pi is a probability distribution on S. The ability to sample efficiently from S according to \pi can lead to polynomial time approximate solutions to computationally hard problems. Without getting into too much detail, I will discuss examples of how Markov Chains can be used to sample approximately uniformly from S, and how such sampling can be used to estimate |S|. Examples may include the Knapsack Problem and card shuffling.