TY - GEN

T1 - Every poset has a good comparison

AU - Kahn, Jeff

AU - Saks, Michael

N1 - Funding Information:
in part by NSF Grant MCS83-01867
Publisher Copyright:
© 1984 ACM.

PY - 1984/12/1

Y1 - 1984/12/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=80053359214&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80053359214&partnerID=8YFLogxK

U2 - 10.1145/800057.808694

DO - 10.1145/800057.808694

M3 - Conference contribution

AN - SCOPUS:80053359214

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 299

EP - 301

BT - Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984

PB - Association for Computing Machinery

T2 - 16th Annual ACM Symposium on Theory of Computing, STOC 1984

Y2 - 30 April 1984 through 2 May 1984

ER -