Sequential Importance Sampling for Counting Linear ExtensionsIsabel Beichl
Applied and Computational Mathematics (ACMD), ITL, NIST
Tuesday, November 8, 2016 15:00-16:00,
Counting the number of topological sorts of a DAG is a well-known NP hard problem, important in in scheduling, and computational linear algebra. Because the problem is hard, approximations must be used. Monte Carlo methods for approximating using MCMC are known but they are not practical for real-world computation as they have complexity O(n$^6$).
We will describe an alternate practical method based on sequential importance sampling. Success using SIS depends on designing an importance function that "knows" the search tree. We describe a robust importance function related to Moebius inversion. One interesting property is that our approximation is exact in case the DAG is a forest.
Speaker Bio: Isabel Beichl works on probabalistic methods for measuring data that can be modeled as a network. Prior to coming to NIST, she taught at Goucher College and did UNIX development at Bell Laboratories. Her PhD is in mathematics from Cornell.
Contact: W. Griffin
Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.