Return to Colloquia & Seminar listing
Applications of Markov Chains to Combinatorics
Student-Run Discrete Mathematics| Speaker: | David Sivakoff, UC Davis |
| Location: | 2112 MSB |
| Start time: | Thu, Jan 31 2008, 3:10PM |
Description
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.