nach oben

Journal of Combinatorial Optimization

Erschienen in:

16.11.2017

The Best-or-Worst and the Postdoc problems

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

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider two variants of the secretary problem, the Best-or-Worst and the Postdoc problems, which are closely related. First, we prove that both variants, in their standard form with binary payoff 1 or 0, share the same optimal stopping rule. We also consider additional cost/perquisites depending on the number of interviewed candidates. In these situations the optimal strategies are very different. Finally, we also focus on the Best-or-Worst variant with different payments depending on whether the selected candidate is the best or the worst.

Vorheriger Artikel Minimal path decomposition of complete bipartite graphs

Nächster Artikel Sparse multipartite graphs as partition universal for graphs with bounded degree

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 SODA, pp 434–443

Bearden JN (2006) A new secretary problem with rank-based selection and cardinal payoffs. J Math Psychol 50:58–59MathSciNetCrossRefMATH

Daley DJ, Kendall DG (1965) Stochastic rumours. J Inst Math Appl 1:42–55MathSciNetCrossRef

Dynkin EB (1963) The optimum choice of the instant for stopping a markov process. Sov Math Dokl 4:627–629MATH

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

Ferguson TS (1992) The best-choice problems with dependent criteria. Contemp Math 25:135–151MathSciNetCrossRefMATH

Ferguson TS, Hardwick JP, Tamaki M (1991) Maximizing the duration of owning a relatively best object. In: Ferguson T, Samuels S (eds) Contemporary mathematics: strategies for sequential search and selection in real time, vol 125. American Mathematics Association, Washington, pp 37–58CrossRef

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

Garrod B, Morris R (2012) 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

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

Lebensztayn E, Machado FP, Rodríguez PM (2011) Limit theorems for a general stochastic rumour model. SIAM J Appl Math 71(4):1476–1486MathSciNetCrossRefMATH

Lindley DV (1961) Dynamic programming and decision theory. J R Stat Soc Ser C (Appl Stat) 10(1):39–51MathSciNetMATH

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

Soto JA (2011) Matroid secretary problem in the random assignment model. In: Proceedings of the SODA, pp 1275–1284

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

Szajowski KA (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 (unpublished)

Titel: The Best-or-Worst and the Postdoc problems
verfasst von: L. Bayón
P. Fortuny Ayuso
J. M. Grau
A. M. Oller-Marcén
M. M. Ruiz
Publikationsdatum: 16.11.2017
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2018
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-017-0203-4

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 3/2018

Online covering salesman problem

The Wiener index of Sierpiński-like graphs

Minimal path decomposition of complete bipartite graphs

Critical objective function values in linear sum assignment problems

Sparse multipartite graphs as partition universal for graphs with bounded degree

Neighbor sum distinguishing list total coloring of subcubic graphs