Partially ordered secretaries

DOI10.1214/ECP.V15-1579MaRDI QIDQ638228zbMATH OpenOpenAlexFDO

Authors Johan Wästlund, Ragnar Freij-Hollanti

Publication date 9 September 2011

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.3310, http://www.emis.de/journals/EJP-ECP/_ejpecp/ECP/viewarticlec958.html

zbMATH Keywords

partial ordersecretary problembest choice problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Management decision making, including multiple objectives (90B50) Randomized algorithms (68W20) Combinatorial probability (60C05) Combinatorics of partially ordered sets (06A07)

Abstract: The elements of a finite nonempty partially ordered set are exposed at independent uniform times in $[0,1]$ to a selector who, at any given time, can see the structure of the induced partial order on the exposed elements. The selector's task is to choose online a maximal element. This generalizes the classical linear order secretary problem, for which it is known that the selector can succeed with probability $1/e$ and that this is best possible. We describe a strategy for the general problem that achieves success probability $1/e$ for an arbitrary partial order.

Recommendations

• The secretary problem on an unknown poset
• The best-choice problem for partially ordered objects.
• The best choice problem for a union of two linear orders with common maximum
• Secretary Problems with Non-Uniform Arrival Order
• On a universal best choice algorithm for partially ordered sets

Cited in

(23)

• Monotone Case for an Extended Process
• The best choice problem for a union of two linear orders with common maximum
• Secretary problem with hidden information; searching for a high merit candidate
• The best-or-worst and the postdoc problems with random number of candidates
• An optimal algorithm for stopping on the element closest to the center of an interval
• A new look at the returning secretary problem
• The best-or-worst and the postdoc problems
• An efficient algorithm for stopping on a sink in a directed graph
• The best choice problem for posets; colored complete binary trees
• Query-based selection of optimal candidates under the Mallows model
• Secretary Problems with Non-Uniform Arrival Order
• Percolation and best-choice problem for powers of paths
• The secretary problem on an unknown poset
• The best choice problem for upward directed graphs
• From directed path to linear order -- the best choice problem for powers of directed path
• Optimal stopping in a search for a vertex with full degree in a random graph
• On a universal best choice algorithm for partially ordered sets
• Where should you park your car? The $\frac{1}{2}$ rule
• The best-choice problem for partially ordered objects.
• Counting embeddings of rooted trees into families of rooted trees
• Optimal stopping for many connected components in a graph
• Maximizing the expected number of components in an online search of a graph
• A Secretary Problem with Many Lives

This page was built for publication: Partially ordered secretaries

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