The solution of a generalized secretary problem via analytic expressions

DOI10.1007/S10878-016-0050-8MaRDI QIDQ2012898zbMATH OpenOpenAlexWikidataFDO

Authors Adam Woryna

Publication date 3 August 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

optimal stoppingcombinatorial identitysecretary problemoptimal sequenceanalytic expression

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Applications of statistics to social sciences (62P25) Combinatorial optimization (90C27) Combinatorial probability (60C05) Combinatorial identities, bijective combinatorics (05A19) Applications of hypergeometric functions (33C90)

Abstract: Given integers $1leqk<n$, the Gusein-Zade version of a generalized secretary problem is to choose one of the $k$ best of $n$ candidates for a secretary, which are interviewing in random order. The stopping rule in the selection is based only on the relative ranks of the successive arrivals. It is known that the best policy can be described by a non--decreasing sequence $(s_1,ldots,s_k)$ of integers with $lleq{s}_l<n$ for every $1leqlleqk$, and conversely, any such a sequence determines the general structure of the best policy. We found a finite analytic expression for the probability of success when using the optimal policy with a sequence $(s_1,ldots,s_k)$. We also study the problem of the construction of the optimal sequence, i.e. a sequence which maximizes the corresponding probability of success. We discovered finite analytic expressions which enable to calculate the elements $s_l$ of an optimal sequence one by one, from $l=k$ to $l=1$. Until now, such expressions were derived separately, and only for the values $kleq3$.

Recommendations

• APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM
• Some Extensions of Generalized Secretary Problem
• A generalized secretary problem
• The Secretary Problem and Its Extensions: A Review
• Improved algorithms and analysis for secretary problems and generalizations
• Secretary Problems via Linear Programming
• Secretary Problems via Linear Programming
• The Secretary Problem with Optimal Assignment
• Remarks on the Secretary Problem

Cites work

• scientific article; zbMATH DE number 3122709 (Why is no real title available?)
• A unified approach to a class of best choice problems with an unknown number of options
• APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM
• Dynamic Programming and Decision Theory
• Exact results for a secretary problem
• Improved algorithms and analysis for secretary problems and generalizations
• On an optimal stopping problem of Gusein-Zade
• Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
• Secretary Problems via Linear Programming
• Solving multi-choice secretary problem in parallel: an optimal observation-selection protocol
• The Secretary Problem and Its Extensions: A Review

Cited in

(10)

• Conditional evaluations of sums of sample maxima and records
• scientific article; zbMATH DE number 4031386 (Why is no real title available?)
• scientific article; zbMATH DE number 3999700 (Why is no real title available?)
• Progressive stopping heuristics that excel in individual and competitive sequential search
• scientific article; zbMATH DE number 572375 (Why is no real title available?)
• Secretary Problems via Linear Programming
• Secretary Problems via Linear Programming
• APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM
• A unified approach for solving sequential selection problems
• A satisficing policy of the secretary problem: theory and simulation

This page was built for publication: The solution of a generalized secretary problem via analytic expressions

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