APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM

DOI10.1017/S026996481000032XzbMATH Open1216.60035arXiv1009.0626OpenAlexW2115230768MaRDI QIDQ3000391FDOQ3000391

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• Title not available (Why is that?)
• Progressive stopping heuristics that excel in individual and competitive sequential search
• The solution of a generalized secretary problem via analytic expressions
• Robust Algorithms for the Secretary Problem
• Secretary Problems via Linear Programming
• Secretary Problems via Linear Programming
• A unified approach for solving sequential selection problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• A generalization of the classical secretary problem: dependent arrival sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)