Using TPA to count linear extensions

Details Using TPA to count linear extensions Using TPA to count linear extensions

2010-10-24

arxiv.org/abs/1010.4981v1

Mathematics

Probability

12 pages, 4 algorithms

Scientific paper

A linear extension of a poset $P$ is a permutation of the elements of the set that respects the partial order. Let $L(P)$ denote the number of linear extensions. It is a #P complete problem to determine $L(P)$ exactly for an arbitrary poset, and so randomized approximation algorithms that draw randomly from the set of linear extensions are used. In this work, the set of linear extensions is embedded in a larger state space with a continuous parameter ?. The introduction of a continuous parameter allows for the use of a more efficient method for approximating $L(P)$ called TPA. Our primary result is that it is possible to sample from this continuous embedding in time that as fast or faster than the best known methods for sampling uniformly from linear extensions. For a poset containing $n$ elements, this means we can approximate $L(P)$ to within a factor of $1 + \epsilon$ with probability at least $1 - \delta$ using an expected number of random bits and comparisons in the poset which is at most $O(n^3(ln n)(ln L(P))\epsilon^{-2}\ln \delta^{-1}).$

Affiliated with

Also associated with

No associations

Rating

Using TPA to count linear extensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Using TPA to count linear extensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using TPA to count linear extensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-277850