On a universal best choice algorithm for partially ordered sets
- 4 September 2007
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 32 (3) , 263-273
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. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008Keywords
Funding Information
- KBN (3T11C01126)
This publication has 6 references indexed in Scilit:
- The best-choice problem for partially ordered objectsOperations Research Letters, 1999
- Partial-order analogue of the secretary problem the binary tree caseDiscrete Mathematics, 1998
- Multicriteria extensions of the best choice problem: sequential selection without linear order1992
- Who Solved the Secretary Problem?Statistical Science, 1989
- Efficient stopping of a random series of partially ordered points1980
- Dynamic Programming and Decision TheoryJournal of the Royal Statistical Society Series C: Applied Statistics, 1961