Applied Computational Mathematics Division


Up

Sequential Importance Sampling for Counting Linear Extensions

Isabel Beichl
Applied and Computational Mathematics (ACMD), ITL, NIST

Tuesday, November 8, 2016 15:00-16:00,
Building 225, Room B111
Gaithersburg
Tuesday, November 8, 2016 13:00-14:00,
Room 4072
Boulder

Abstract: A linear extension of a partially ordered set is a linear ordering of the vertices that respects the poset ordering. Any directed acyclic graph (DAG) defines a poset where vertex v precedes vertex w in the poset if w is reachable from v via a directed path. A linear ordering for the vertices of a DAG , called a topological sort, is equivalent to a linear extension for the associated DAG.

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.

Presentation Slides: PDF

Contact: W. Griffin

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.