Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2506.14725 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908410866302976 |
|---|---|
| author | Huber, Mark |
| author_facet | Huber, Mark |
| contents | A \emph{linear extension} of a partial order \(\preceq\) over items \(A = \{ 1, 2, \ldots, n \}\) is a permutation \(σ\) such that for all \(i < j\) in \(A\), it holds that \(\neg(σ(j) \preceq σ(i))\). Consider the problem of generating uniformly from the set of linear extensions of a partial order. The best method currently known uses \(O(n^3 \ln(n))\) operations and \(O(n^3 \ln(n)^2)\) iid fair random bits to generate such a permutation. This paper presents a method that generates a uniform linear extension using only \(2.75 n^3 \ln(n)\) operations and \( 1.83 n^3 \ln(n) \) iid fair bits on average. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generating uniform linear extensions using few random bits Huber, Mark Computational Complexity Probability Computation 68W20 G.3 A \emph{linear extension} of a partial order \(\preceq\) over items \(A = \{ 1, 2, \ldots, n \}\) is a permutation \(σ\) such that for all \(i < j\) in \(A\), it holds that \(\neg(σ(j) \preceq σ(i))\). Consider the problem of generating uniformly from the set of linear extensions of a partial order. The best method currently known uses \(O(n^3 \ln(n))\) operations and \(O(n^3 \ln(n)^2)\) iid fair random bits to generate such a permutation. This paper presents a method that generates a uniform linear extension using only \(2.75 n^3 \ln(n)\) operations and \( 1.83 n^3 \ln(n) \) iid fair bits on average. |
| title | Generating uniform linear extensions using few random bits |
| topic | Computational Complexity Probability Computation 68W20 G.3 |
| url | https://arxiv.org/abs/2506.14725 |