Every poset has a good comparison

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We show that any finite partially ordered set P contains a pair of elements x and y such that the proportion of linear extensions of P in which x lies below y is between 3/11 and 8/11. A consequence is that the information-theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: if X is a totally ordered set about which we are given some partial information, and if e(X) is the number of total orderings of X compatible with this partial information, then it is possible to sort X using no more than c log2e(X) comparisons (c=2.17).

Original languageEnglish (US)
Title of host publicationProceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984
PublisherAssociation for Computing Machinery
Pages299-301
Number of pages3
ISBN (Electronic)0897911334
DOIs
StatePublished - Dec 1 1984
Event16th Annual ACM Symposium on Theory of Computing, STOC 1984 - Washington, United States
Duration: Apr 30 1984May 2 1984

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other16th Annual ACM Symposium on Theory of Computing, STOC 1984
Country/TerritoryUnited States
CityWashington
Period4/30/845/2/84

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Every poset has a good comparison'. Together they form a unique fingerprint.

Cite this