×

Using TPA to count linear extensions. (English) Zbl 1410.68261

Summary: A linear extension of a poset \(P\) is a permutation of the elements of the set that respects the partial order. Let \(L(P)\) be the set of linear extensions. It is a #P complete problem to determine the size of \(L(P)\) exactly for an arbitrary poset, and so randomized approximation algorithms are used that employ samples that are uniformly drawn from the set of linear extensions. In this work, a new randomized approximation algorithm is proposed where the linear extensions are not uniformly drawn, but instead come from a distribution indexed by a continuous parameter \(\beta\). The introduction of \(\beta\) allows for the use of a more efficient method for approximating \({\#} L(P)\) called \(\mathsf{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 \(O(n^3(\ln n)(\ln {\#} L(P))^2 \epsilon^{- 2} \ln \delta^{- 1})\) expected number of random uniforms and comparisons.

MSC:

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

References:

[1] Alon, N.; Spencer, J. H., The Probabilistic Method, (2008), John Wiley & Sons, Inc. · Zbl 1148.05001
[2] Brightwell, G.; Winkler, P., Counting linear extensions, Order, 8, 3, 225-242, (1991) · Zbl 0759.06001
[3] Bubley, R.; Dyer, M., Faster random generation of linear extensions, Discrete Math., 201, 81-88, (1999) · Zbl 0934.65005
[4] Durrett, R., Probability: Theory and Examples, (2005), Brooks/Cole · Zbl 1202.60002
[5] Fishburn, P. C.; Gehrlein, W. V., A comparative analysis of methods for constructing weak orders from partial orders, J. Math. Sociol., 4, 93-102, (1975) · Zbl 0324.68071
[6] Huber, M., Perfect sampling using bounding chains, Ann. Appl. Probab., 14, 2, 734-753, (2004) · Zbl 1052.60057
[7] Huber, M., Fast perfect sampling from linear extensions, Discrete Math., 306, 420-428, (2006) · Zbl 1090.60064
[8] Huber, M. L.; Schott, S., Using TPA for Bayesian inference, Bayesian Stat., 9, (2010)
[9] Huber, M. L.; Schott, S., Random construction of interpolating sets for high dimensional integration, J. Appl. Probab., 51, 1, 92-105, (2014) · Zbl 1291.60205
[10] Jerrum, M.; Valiant, L.; Vazirani, V., Random generation of combinatorial structures from a uniform distribution, Theor. Comput. Sci., 43, 169-188, (1986) · Zbl 0597.68056
[11] Karzonov, A.; Khachiyan, L., On the conductance of order Markov chains, Order, 8, 1, 7-15, (1991) · Zbl 0736.06002
[12] Morton, J.; Pachter, L.; Shiu, A.; Sturmfels, B.; Wienand, O., Convex rank tests and semigraphoids, SIAM J. Discrete Math., 23, 2, 1117-1134, (2009) · Zbl 1198.62038
[13] Propp, J. G.; Wilson, D. B., Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Struct. Algorithms, 9, 1-2, 223-252, (1996) · Zbl 0859.60067
[14] Štefankovič, D.; Vempala, S.; Vigoda, E., Adaptive simulated annealing: a near-optimal connection between sampling and counting, J. ACM, 56, 3, 1-36, (2009) · Zbl 1325.68198
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.