nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.12.2018

The Best-or-Worst and the Postdoc problems with random number of candidates

verfasst von: L. Bayón, P. Fortuny, J. Grau, A. M. Oller-Marcén, M. M. Ruiz

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we consider two variants of the Secretary problem: The Best-or-Worst and the Postdoc problems. We extend previous work by considering that the number of objects is not known and follows either a discrete Uniform distribution \({\mathcal {U}}[1,n]\) or a Poisson distribution \({\mathcal {P}} (\lambda )\). We show that in any case the optimal strategy is a threshold strategy, we provide the optimal cutoff values and the asymptotic probabilities of success. We also put our results in relation with closely related work.

Vorheriger Artikel Hitting a path: a generalization of weighted connectivity via game theory

Nächster Artikel Two-stage stochastic days-off scheduling of multi-skilled analysts with training options

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Babaioff M, Immorlica N, Kleinberg R (2007) Matroids, secretary problems, and online mechanisms. In: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms. ACM, New York, pp 434–443

Bayón L, Fortuny Ayuso P, Grau JM, Oller-Marcén AM, Ruiz MM (2018) The Best-or-Worst and the Postdoc problems. J Comb Optim 35(3):703–723MathSciNetCrossRefMATH

Bruss FT (1987) On an optimal selection problem of Cowan and Zabczyk. J Appl Probab 24(4):918–928MathSciNetCrossRefMATH

Bruss FT (2000) Sum the odds to one and stop. Ann Probab 28(3):1384–1391MathSciNetCrossRefMATH

Bruss FT (2003) A note on bounds for the odds theorem of optimal stopping. Ann Probab 31(4):1859–1861MathSciNetCrossRefMATH

Cowan R, Zabczyk J (1978) An optimal selection problem associated with the Poisson process. Teor Veroyatnost i Primenen 23(3):606–614MathSciNetMATH

Dendievel R (2013) New developments of the odds-theorem. Math Sci 38(2):111–123MathSciNetMATH

Dendievel R (2015) Weber’s optimal stopping problem and generalizations. Stat Probab Lett 97:176–184MathSciNetCrossRefMATH

Dynkin EB (1963) Optimal choice of the stopping moment of a Markov process. Dokl Akad Nauk SSSR 150:238–240MathSciNet

Ferguson TS (1989) Who solved the secretary problem? Stat Sci 4(3):282–296MathSciNetCrossRefMATH

Ferguson TS (1992) Best-choice problems with dependent criteria. Strategies for sequential search and selection in real time. In: Bruss FT, Ferguson TS, Samuels S (eds) Proceedings of the AMS-IMS-SIAM joint summer research conference (Amherst, MA, 1990), contemporary mathematics, vol 125. American Mathematical Society, Providence, RI, pp 135–151

Ferguson TS, Hardwick JP, Tamaki M (1992) Maximizing the duration of owning a relatively best object. Strategies for sequential search and selection in real time. In: Bruss FT, Ferguson TS, Samuels S (eds) Proceedings of the AMS-IMS-SIAM joint summer research conference (Amherst, MA, 1990), contemporary mathematics, vol 125. American Mathematical Society, Providence, RI, pp 37–58

Freij R, Wastlund J (2010) Partially ordered secretaries. Electron. Commun. Probab. 15:504–507MathSciNetCrossRefMATH

Garrod B, Morris R (2013) The secretary problem on an unknown poset. Random Struct Algorithms 43(4):429–451MathSciNetCrossRefMATH

Georgiou N, Kuchta M, Morayne M, Niemiec J (2008) On a universal best choice algorithm for partially ordered sets. Random Struct Algorithms 32:263–273MathSciNetCrossRefMATH

Gharan SO, Vondrák J (2013) On Variants of the Matroid Secretary Problem. J Algorithmica 67(4):472–497MathSciNetCrossRefMATH

Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J Am Stat Assoc 61:35–73MathSciNetCrossRef

Havil J (2003) Optimal choice. Gamma: exploring Euler’s constant. Princeton University Press, Princeton, pp 34–138MATH

Lindley DV (1961) Dynamic programming and decision theory. Appl Stat 10:39–51MathSciNetCrossRefMATH

Louchard G (2017) A refined and asymptotic analysis of optimal stopping problems of Bruss and Weber. Math Appl 45(2):95–118MathSciNet

Rose JS (1982) A problem of optimal choice and assignment. Oper Res 30(1):172–181MathSciNetCrossRefMATH

Presman ÈL, Sonin IM (1972) The problem of best choice in the case of a random number of objects. Teor Verojatnost i Primenen 17:695–706MathSciNetMATH

Soto JA (2013) Matroid secretary problem in the random-assignment model. Siam J Comput 42(1):178–211MathSciNetCrossRefMATH

Szajowski K (1982) Optimal choice problem of a-th object. Matem Stos 19:51–65MATH

Szajowski K (2007) A game version of the Cowan–Zabczyk–Bruss’ problem. Stat Probab Lett 77(17):1683–1689MathSciNetCrossRefMATH

Szajowski K (2009) A rank-based selection with cardinal payoffs and a cost of choice. Sci Math Jpn 69(2):285–293MathSciNetMATH

Vanderbei RJ (1983) The Postdoc variant of the secretary problem. http://www.princeton.edu/rvdb/tex/PostdocProblem/PostdocProb.pdf. Accessed 01 July 2018 (unpublished)

Titel: The Best-or-Worst and the Postdoc problems with random number of candidates
verfasst von: L. Bayón
P. Fortuny
J. Grau
A. M. Oller-Marcén
M. M. Ruiz
Publikationsdatum: 01.12.2018
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2019
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0367-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2019

Non-adaptive group testing on graphs with connectivity

On the randomized online strategies for the k-Canadian traveler problem

Online interval scheduling on two related machines: the power of lookahead

Optimal channel assignment with list-edge coloring

Model and algorithm of routes planning for emergency relief distribution in disaster management with disaster information update

Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem