The secretary problem on an unknown poset

DOI10.1002/RSA.20466zbMATH Open1278.90192arXiv1107.1379OpenAlexW2964062927MaRDI QIDQ2868083FDOQ2868083

Authors: Bryn Garrod, Robert Morris 

Publication date: 23 December 2013

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

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.

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

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

zbMATH Keywords

partially ordered setssecretary problemoptimal choice

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50)

Cites Work

• Who solved the secretary problem
• A decomposition theorem for partially ordered sets
• Title not available (Why is that?)
• Partially ordered secretaries
• On a universal best choice algorithm for partially ordered sets
• Partial-order analogue of the secretary problem: The binary tree case
• The best-choice problem for partially ordered objects.
• Multicriterial problem of optimum stopping of the selection process
• How to choose the best twins

Cited In (17)

• Title not available (Why is that?)
• The best-or-worst and the postdoc problems with random number of candidates
• A new look at the returning secretary problem
• From Directed Path to Linear Order---The Best Choice Problem for Powers of Directed Path
• 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
• 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
• Maximizing the expected number of components in an online search of a graph
• Monotone Case for an Extended Process

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)