Using TPA to count linear extensions

DOI10.1016/J.JDA.2018.04.001MaRDI QIDQ1757459zbMATH OpenOpenAlexFDO

Authors Jacqueline Banks, Scott M. Garrabrant, Mark Huber, Anne Perizzolo

Publication date 4 January 2019

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.4981

zbMATH Keywords

\#P-complete problemsapproximation algorithmMonte Carlopartial ordersperfect sampling

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Approximation algorithms (68W25)

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(lnn)(lnL(P))epsilo{n}^{-2}lndelt{a}^{-1}).$

Recommendations

• Counting linear extensions
• Approximating the number of linear extensions
• Counting linear extensions: parameterizations by treewidth
• Counting linear extensions: parameterizations by treewidth
• Counting extensions
• Counting extensions revisited
• A faster tree-decomposition based algorithm for counting linear extensions
• A faster tree-decomposition based algorithm for counting linear extensions
• Counting linear extensions of restricted posets
• scientific article; zbMATH DE number 16221

Cites work

• A comparative analysis of methods for constructing weak orders from partial orders
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Convex rank tests and semigraphoids
• Counting linear extensions
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Fast perfect sampling from linear extensions
• Faster random generation of linear extensions
• scientific article; zbMATH DE number 5819433 (Why is no real title available?)
• On the conductance of order Markov chains
• Perfect sampling using bounding chains.
• Random Construction of Interpolating Sets for High-Dimensional Integration
• Random generation of combinatorial structures from a uniform distribution
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(4)

• A faster tree-decomposition based algorithm for counting linear extensions
• A Sequential Importance Sampling Algorithm for Counting Linear Extensions
• Fast and simple sorting using partial information
• A faster tree-decomposition based algorithm for counting linear extensions

This page was built for publication: Using TPA to count linear extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1757459)