APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM

DOI10.1017/S026996481000032XMaRDI QIDQ3000391zbMATH OpenOpenAlexFDO

Authors Chris Dietz, Dinard van der Laan, A. Ridder

Publication date 18 May 2011

Published in Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40)

Abstract: A version of the classical secretary problem is studied, in which one is interested in selecting one of the b best out of a group of n differently ranked persons who are presented one by one in a random order. It is assumed that b is a preassigned (natural) number. It is known, already for a long time, that for the optimal policy one needs to compute b position thresholds, for instance via backwards induction. In this paper we study approximate policies, that use just a single or a double position threshold, albeit in conjunction with a level rank. We give exact and asymptotic (as n tends to infinity) results, which show that the double-level policy is an extremely accurate approximation.

Recommendations

• Some Extensions of Generalized Secretary Problem
• A generalized secretary problem
• The solution of a generalized secretary problem via analytic expressions
• Improved algorithms and analysis for secretary problems and generalizations
• The Secretary Problem and Its Extensions: A Review
• scientific article; zbMATH DE number 4031386
• The Secretary Problem with Optimal Assignment
• scientific article; zbMATH DE number 1766760

Cites work

• Exact results for a secretary problem
• MARKOV PROCESSES AND RELATED PROBLEMS OF ANALYSIS
• On an optimal stopping problem of Gusein-Zade

Cited in

(14)

• scientific article; zbMATH DE number 3999700 (Why is no real title available?)
• Progressive stopping heuristics that excel in individual and competitive sequential search
• The solution of a generalized secretary problem via analytic expressions
• A unified approach for solving sequential selection problems
• Secretary Problems via Linear Programming
• Robust Algorithms for the Secretary Problem
• Secretary Problems via Linear Programming
• scientific article; zbMATH DE number 7650251 (Why is no real title available?)
• scientific article; zbMATH DE number 572375 (Why is no real title available?)
• A generalization of the classical secretary problem: dependent arrival sequences
• scientific article; zbMATH DE number 4031386 (Why is no real title available?)
• scientific article; zbMATH DE number 4106644 (Why is no real title available?)
• Dynamic programming and the secretary problem
• Optimal stopping of a random sequence with unknown distribution

This page was built for publication: APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM

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