The secretary problem with distributions

DOI10.1007/978-3-031-06901-7_32MaRDI QIDQ2164728zbMATH OpenOpenAlexFDO

Authors Pranav Nuti

Publication date 16 August 2022

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

zbMATH Keywords

incomplete informationnegative dependenceonline algorithmssecretary problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: We study a variant of the secretary problem where candidates come from independent, not necessarily identical distributions known to us, and show that we can do at least as well as in the IID setting. This resolves a conjecture of Esfandiari et al.

Recommendations

• The secretary problem on an unknown poset
• A unified approach to a class of best choice problems with an unknown number of options
• Minimax-optimal stop rules and distributions in secretary problems
• Secretary Problems with Non-Uniform Arrival Order
• Secretary problem

Cites work

• Conditional negative association for competing urns
• scientific article; zbMATH DE number 7650408 (Why is no real title available?)
• Posted price mechanisms and optimal threshold strategies for random arrivals
• Prophet secretary
• Prophet secretary through blind strategies
• The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
• Towards a theory of negative dependence.

Cited in

(5)

• The Secretary's Packet Problem
• The Secretary Problem—An Update
• Uniformly bounded regret in the multisecretary problem
• Secretaries with advice
• Oracle-augmented prophet inequalities

This page was built for publication: The secretary problem with distributions

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