Second REU paper up on the archive

The second paper to come out of the REU I ran this summer is now up on the arXiv here.  This paper brings a discrete problem:  counting the number of linear extensions of a partially ordered set into a continuous framework so that TPA can be utilized.  This paper has been submitted.

Title:  Using TPA to count linear extensions

(Submitted on 24 Oct 2010)
Abstract

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}).$

 

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: