The secretary problem on an unknown poset

DOI10.1002/RSA.20466MaRDI QIDQ2868083zbMATH OpenOpenAlexFDO

Authors Bryn Garrod, Robert Morris

Publication date 23 December 2013

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.1379

zbMATH Keywords

partially ordered setssecretary problemoptimal choice

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50)

Abstract: We consider generalizations of the classical secretary problem, also known as the problem of optimal choice, to posets where the only information we have is the size of the poset and the number of maximal elements. We show that, given this information, there is an algorithm that is successful with probability at least $frac1e$. We conjecture that if there are $k$ maximal elements and $kgeq2$ then this can be improved to $sqrt[k-1]frac1k$, and prove this conjecture for posets of width $k$. We also show that no better bound is possible.

Recommendations

• Partially ordered secretaries
• A unified approach to a class of best choice problems with an unknown number of options
• Secretary problem
• The Secretary Problem with a Choice Function
• scientific article; zbMATH DE number 3999700

Cites work

• scientific article; zbMATH DE number 52077 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• How to choose the best twins
• Multicriterial problem of optimum stopping of the selection process
• On a universal best choice algorithm for partially ordered sets
• Partial-order analogue of the secretary problem: The binary tree case
• Partially ordered secretaries
• The best-choice problem for partially ordered objects.
• Who solved the secretary problem

Cited in

(20)

• Monotone Case for an Extended Process
• The best choice problem for a union of two linear orders with common maximum
• scientific article; zbMATH DE number 4033475 (Why is no real title available?)
• The best-or-worst and the postdoc problems with random number of candidates
• A new look at the returning secretary problem
• The best-or-worst and the postdoc problems
• Weber's optimal stopping problem and generalizations
• The best choice problem for posets; colored complete binary trees
• Query-based selection of optimal candidates under the Mallows model
• Percolation and best-choice problem for powers of paths
• The best choice problem for upward directed graphs
• From directed path to linear order -- the best choice problem for powers of directed path
• The secretary problem with distributions
• On a universal best choice algorithm for partially ordered sets
• Partially ordered secretaries
• Secretary problem: graphs, matroids and greedoids
• Where should you park your car? The $\frac{1}{2}$ rule
• Counting embeddings of rooted trees into families of rooted trees
• Hiring strategies
• Maximizing the expected number of components in an online search of a graph

This page was built for publication: The secretary problem on an unknown poset

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868083)