A Sequential Importance Sampling Algorithm for Counting Linear Extensions
From MaRDI portal
Abstract: In recent decades, a number of profound theorems concerning approximation of hard counting problems have appeared. These include estimation of the permanent, estimating the volume of a convex polyhedron, and counting (approximately) the number of linear extensions of a partially ordered set. All of these results have been achieved using probabilistic sampling methods, specifically Monte Carlo Markov Chain (MCMC) techniques. In each case, a rapidly mixing Markov chain is defined that is guaranteed to produce, with high probability, an accurate result after only a polynomial number of operations. Although of polynomial complexity, none of these results lead to a practical computational technique, nor do they claim to. The polynomials are of high degree and a non-trivial amount of computing is required to get even a single sample. Our aim in this paper is to present practical Monte Carlo methods for one of these problems, counting linear extensions. Like related work on estimating the coefficients of the reliability polynomial, our technique is based on improving the so-called Knuth counting algorithm by incorporating an importance function into the node selection technique giving a sequential importance sampling (SIS) method. We define and report performance on two importance functions.
Recommendations
Cites work
- Approximating the permanent via importance sampling with application to the dimer covering problem
- Counting linear extensions
- Estimating the Efficiency of Backtrack Programs
- Fast sequential importance sampling to estimate the graph reliability polynomial
- Faster random generation of linear extensions
- Generalized multiple importance sampling
- Identifying clusters in spatial data via sequential importance sampling
- Linear extensions of a random partial order
- Mixing times of lozenge tiling and card shuffling Markov chains
- Permanental generating functions and sequential importance sampling
- The Transitive Reduction of a Directed Graph
- Topological sorting of large networks
- Using TPA to count linear extensions
Cited in
(5)- Counting linear extensions
- Stochastic enumeration with importance sampling
- Sequential Monte Carlo for counting vertex covers in general graphs
- Multisampling: a new approach to uniform sampling and approximate counting
- Sequential importance sampling for estimating expectations over the space of perfect matchings
This page was built for publication: A Sequential Importance Sampling Algorithm for Counting Linear Extensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039921)
