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 contribution | On a universal best choice algorithm for partially ordered sets |
---|---|
Original language | English |
Pages (from-to) | 263 - 273 |
Number of pages | 11 |
Journal | Random Structures and Algorithms |
Volume | 32 (3) |
DOIs | |
Publication status | Published - May 2008 |