1
$\begingroup$

I'm looking for one of two closely related algorithms. In both, you have a list of elements, of which you have to choose one by some scoring method. In the first variation, the list is infinite and you can't go trough it all, but you can choose any item. In the second, you must choose to accept or reject an item permanently, so if you get to the end, and the last item is a dud, you're stuck with it.

You have no prior knowledge of the range of scores found in the list. As you look at elements of the list, continuously adapt your threshold for acceptance, until you are able to choose an item without having exhausted the list.

For the second variation (finite list), I've seen it in some semi-joking context about dating, where you spend up until age 35 dating people as "samples" and rejecting them all in due time, then past age 35, take the first person who is above the threshold learned from the previous samples.

$\endgroup$
1
  • 1
    $\begingroup$ The second is known classically as the secretary problem (in the context of interviewing a sequence of candidates for a position as a secretary). $\endgroup$ – mhum Sep 18 '18 at 20:12
2
$\begingroup$

These problems are in the field of optimal stopping theory. There are a large number of approaches to the problem, which can be found using this term.

The example about dating appears in Hannah Fry's Ted Talk "The Mathematics of Love"

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.