The solution of a generalized secretary problem via analytic expressions

DOI10.1007/S10878-016-0050-8zbMATH Open1406.90110arXiv1607.07658OpenAlexW3100269656WikidataQ59608693 ScholiaQ59608693MaRDI QIDQ2012898FDOQ2012898

Authors: Adam Woryna 

Publication date: 3 August 2017

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

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• The Secretary Problem and Its Extensions: A Review
• Dynamic Programming and Decision Theory
• Improved algorithms and analysis for secretary problems and generalizations
• A unified approach to a class of best choice problems with an unknown number of options
• On an optimal stopping problem of Gusein-Zade
• Exact results for a secretary problem
• APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM
• Secretary Problems via Linear Programming
• Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol
• Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order

Cited In (10)

• A satisficing policy of the secretary problem: theory and simulation
• Title not available (Why is that?)
• Progressive stopping heuristics that excel in individual and competitive sequential search
• APPROXIMATE RESULTS FOR A GENERALIZED 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?)
• Title not available (Why is that?)

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)