Volume 2014
Article 3
Published by the Department of Computer Science, The University of Chicago.
Near-linear time simulation of linear extensions of a
height-2 poset with bounded interaction
Mark Huber
Claremont McKenna College
Claremont CA
USA
mhuber AT cmc.edu
June 8, 2014
Abstract
A linear extension of a poset $([n],\preceq)$
is a permutation
$\sigma$ such that if $\sigma(i) \preceq \sigma(j)$, then $i \leq j$.
The problem considered here is sampling uniformly
from the set of linear extensions. The best known algorithm for the
general problem requires time $O(n^3\ln n)$.
This work presents the first new method that
is provably faster for a nontrivial class of posets. Specifically,
when the poset
is height-2 (so there do not exist distinct elements with
$i \preceq j \preceq k$)
and has bounded interaction (so for each $i$ there are at most
$\Delta$ elements $i'$ with $i \preceq i'$ or $i' \preceq i$), then the
new algorithm runs in time $O(n\Delta^2 \ln n)$. Such posets arise
naturally as corrugated surfaces on graphs, where $\Delta - 1$ is the
maximum degree of the graph. Therefore, finding corrugated surfaces on
a fixed family of lattices takes $O(n \ln n)$ (near-linear time.) The
ability to sample from the set of linear extensions can be used to build
approximation algorithms for counting the number of linear extensions.
Using the new method, an approximation scheme that counts the number of
linear extensions to within a factor of $1 + \epsilon$ with fixed probability
runs in $O(n^2 \Delta^2 [\ln n]^6\epsilon^{-2})$ time.
- The article: PDF (268 KB)
- Source material: ZIP (84 KB)
- BibTeX entry for this article (306 bytes)
Submitted November 10, 2012, revised May 24, 2014, published June 8,2014.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 2
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2014
Published articles
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif)
Licensed under a Creative Commons Attribution License