Improved algorithms and analysis for secretary problems and generalizations

DOI10.1137/S0895480195290017MaRDI QIDQ2706186zbMATH OpenOpenAlexFDO

Authors Miklós Ajtai, Nimrod Megiddo, Orli Waarts

Publication date 19 March 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480195290017

zbMATH Keywords

dynamic programmingexpected rankexplicit algorithmsmaximizationoptimal stoppingsecretary problems

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Dynamic programming (90C39)

Review text

A family of explicit algorithms for the secretary problems is developed. A lower bound on the trade-off between the probability of selecting the best object and the expected rank of the selected object are derived too.

Recommendations

• Secretary Problems via Linear Programming
• New results for the \(k\)-secretary problem
• A multiple-choice secretary algorithm with applications to online auctions
• The senior and junior secretaries problem
• On Multiple Choice Secretary Problems

Cited in

(24)

• Partial-order analogue of the secretary problem: The binary tree case
• Secretary problems as a source of benchmark bounds
• The solution of a generalized secretary problem via analytic expressions
• A unified approach for solving sequential selection problems
• A new look at the returning secretary problem
• New results for the \(k\)-secretary problem
• APPROXIMATE RESULTS FOR A GENERALIZED SECRETARY PROBLEM
• Improved competitive ratios for submodular secretary problems (extended abstract)
• Prophet secretary
• Online appointment scheduling in the random order model
• Analysis of the ``hiring above the median selection strategy for the hiring problem
• A generalization of the classical secretary problem: dependent arrival sequences
• Optimal, quality-aware scheduling of data consumption in mobile ad hoc networks
• scientific article; zbMATH DE number 3999700 (Why is no real title available?)
• Analysis of the strategy ``hiring above the \(m\)-th best candidate
• Strong algorithms for the ordinal matroid secretary problem
• Submodular secretary problem with shortlists
• scientific article; zbMATH DE number 7077336 (Why is no real title available?)
• Prophet secretary
• scientific article; zbMATH DE number 7650251 (Why is no real title available?)
• Robust Algorithms for the Secretary Problem
• Delay-tolerant delivery of quality information in ad hoc networks
• Algorithms for maximum social welfare of online random trading
• Optimal algorithms for \(k\)-search with application in option pricing

This page was built for publication: Improved algorithms and analysis for secretary problems and generalizations

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