Counting Linear Extensions of a Partially Ordered Set Using Sequential Importance Sampling

What is it about?

This paper introduces a new way to estimate the number of linear extensions of a partially ordered set, using decision trees and sequential importance sampling. A partially ordered set is a collection of objects, together with a collection of rules about which ones must be placed before which other ones. A linear extension is a particular way of ordering all the objects in the set in a way that is compliant with the rules of the partial order. By thinking about which objects can be placed first, and then which can be placed second, third, etc., a branching decision tree can be produced which enumerates all possible ways to order the objects. The number of endpoints on the tree is the number of possible linear extensions. These decision trees are typically extremely large and practically impossible to count, so it is necessary to find efficient ways to estimate how large they are. In this paper, we describe a new algorithm to count them and provide numerical evidence of the efficiency and accuracy of the algorithm.

Featured Image

Why is it important?

The most common applications are in scheduling problems, where the number of linear extensions gives the size of the solution space. For example, if we are trying to find a schedule that is optimal with respect to some cost function, the size of the solution space can be valuable in deciding how to carry out the search. If the solution space is small, then we may be able to perform an exhaustive search for the best order, but if the solution space is large, then we may wish to settle for an approximate solution.

Perspectives