0
$\begingroup$

I came across the following family of online problems:

Given a sequence of values of length n, the maximum value and the minimum value of the sequence, our goal: Given min and max, we want to find a good/best element in an online that if an element of the sequence satisfies some criteria based on min and max accept it and stop the execution, otherwise continue receiving more values.

Does this particular family of problems have a name? it appears to me as some extension of secretary problem with more information/assumptions on the input, or some variant of knapsack problem where you have capacity for 1 item only but I don't know if it has a particular name.

$\endgroup$
10
  • 1
    $\begingroup$ based on max and min, decide a strategy for each value of the sequence to see if we accept it and stop the execution - what does it mean? How min and max are supposed to be used? How do you measure which of the elements is the best to accept? (E.g. why can't you just select the first element?) $\endgroup$
    – Dmitry
    Commented Oct 30, 2021 at 13:49
  • $\begingroup$ @Dmitry how you use min and max, is part of the solution strategy, which is off-topic, you are trying to solve the problem and I am asking if the problem has a name, if someone knows the name of the problem, the info I gave should be enough. Still, To answer your question you could use min and max to compute the average for example. How to measure each element? each element is a value/a weight. if element[i]>avg(min,max) accept it, else keep getting new items $\endgroup$
    – user206904
    Commented Oct 30, 2021 at 13:55
  • $\begingroup$ Did I understand correctly that you want to maximize the value of the accepted element? If so, please edit the post to include this information. $\endgroup$
    – Dmitry
    Commented Oct 30, 2021 at 13:56
  • 1
    $\begingroup$ @Dmitry I edited it. But just so you know, it is completely irrelevant and useless details for someone who knows what that is. This has to do with the solution/strategy, which I don't care about. I am asking if the particular family of online problems have a particular name. if I tell you "does having n elements, and trying to fit them in limited space has a name" the answer is "yes, it's called knapsack", we don't need the details to answer such question. $\endgroup$
    – user206904
    Commented Oct 30, 2021 at 14:04
  • 2
    $\begingroup$ No worries. Saying that you came across it in your research helps understand the context and motivation. I have some advice. Rather than asking for the name of a problem, I generally encourage people to ask how to solve some specific problem, as many problems don't have a standard "name", and that way there are two ways to find a useful answer: either someone describes how to solve the problem, or else someone tell you it is a standard problem that has already been studied (has a "name"). $\endgroup$
    – D.W.
    Commented Nov 2, 2021 at 20:14

1 Answer 1

4
$\begingroup$

Since the goal is to select a single element without receiving further input from a given stream of input, this problem sounds like the optimal stopping problem.

In mathematics, the theory of optimal stopping or early stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance (related to the pricing of American options). A key example of an optimal stopping problem is the secretary problem.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, Your answer is indeed a valid and a correct answer, so I can't really complain about it, but I was hoping to know if it has some more specific name. For instance, The secretary problem has a specific name and it falls under stopping problem. So I was hoping to know if it is just a random stopping problem, or if it has specific name. $\endgroup$
    – user206904
    Commented Oct 30, 2021 at 19:07
  • $\begingroup$ It would be great if there is a specific name. As you noted, this problem appears as some extension of the secretary problem. There is not much room for a named variation between the secretary problem and its natural and direct generalization, the optimal stopping problem. I failed to identify any fundamental difference between the problem you described and the optimal stopping problem. $\endgroup$
    – John L.
    Commented Oct 30, 2021 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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