F. Thomas Bruss ; Guy Louchard - Sequential selection of the k best out of nrankable objects

dmtcs:1291 - Discrete Mathematics & Theoretical Computer Science, October 28, 2016, Vol. 18 no. 3 - https://doi.org/10.46298/dmtcs.1291
Sequential selection of the k best out of nrankable objectsArticle

Authors: F. Thomas Bruss 1; Guy Louchard 2

  • 1 Département de Mathématique [Bruxelles]
  • 2 Département d'Informatique [Bruxelles]

The objective of this paper is to find in a setting of n sequential observations of objects a good online policy to select the k bestof these n uniquely rankable objects. This focus is motivated by the fact that it is hard to find closed form solutions of optimalstrategies for general k and n. Selection is without recall, and the idea is to investigate threshold functions which maintain allpresent information, that is thresholds which are functions of all selections made so far. Our main interest lies in the asymptoticbehaviour of these thresholds as n -> infinity and in the corresponding asymptotic performance of the threshold algorithm.


Volume: Vol. 18 no. 3
Section: Analysis of Algorithms
Published on: October 28, 2016
Accepted on: August 22, 2016
Submitted on: October 28, 2016
Keywords: record-values,unimodality,relative ranks,Multiple stopping ,secretary problem,monotonicity,optimality ,odds-theorem,2010 Mathematics Subject Classification: 60G40 (68W27).,ACM : G,[MATH] Mathematics [math],[INFO] Computer Science [cs]

Consultation statistics

This page has been seen 640 times.
This article's PDF has been downloaded 900 times.