On a universal best choice algorithm for partially ordered sets

N Georgiou, M Kuchta, M Morayne, J Niemiec

Research output: Contribution to journalArticle (Academic Journal)peer-review

23 Citations (Scopus)

Abstract

For the only known universal best choice algorithm for partially ordered sets with known cardinality and unknown order (proposed by J. Preater) we improve the estimation of the lower bound of its chance of success from the hitherto known constant 1/8 to 1/4. We also show that this result is the best possible for this algorithm, i.e., the 1/4 bound cannot be further improved.
Translated title of the contributionOn a universal best choice algorithm for partially ordered sets
Original languageEnglish
Pages (from-to)263 - 273
Number of pages11
JournalRandom Structures and Algorithms
Volume32 (3)
DOIs
Publication statusPublished - May 2008

Bibliographical note

Publisher: Wiley

Fingerprint Dive into the research topics of 'On a universal best choice algorithm for partially ordered sets'. Together they form a unique fingerprint.

Cite this