Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2506.14725 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- 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.