That’s not satisficing because I don’t take the first option alternative that is good enough.
Talking about computational complexity, I would probably put this one in the category of “satisficing,” since this is just a generalization of “good enough” from “objective value” to “convergence criterion.” It could be an optimality gap, the derivative of the objective function of found solutions, time since a new best solution was found, some complicated guess from solution space generalization, or so on.
(Another way to think about this is “acceptability” doesn’t have to apply to just the solution; it can also apply to the search process.)
I would probably put this one in the category of “satisficing,” since this is just a generalization of “good enough” from “objective value” to “convergence criterion.”
You can just as easily put it into the category of “maximizing” since you’re maximizing your expected return (gain—costs).
You can just as easily put it into the category of “maximizing” since you’re maximizing your expected return (gain—costs).
In other frameworks, yes: a biologist or economist would think it natural to talk about real-world maximization (read: improvement) where costs are very relevant to profit.
In the framework of computational complexity, maximization problems are characterized by searching over a set of potential solutions and generating a proof that a particular solution is the best of those solutions. In the worst case where there is no structure on the set, that’s an O(N) operation (start at the first element in the set, compare the element in memory to element i+1 and put the bigger one in memory) on a set that’s typically exponential in problem size. So the generalization of expected return to maximization in this view is proving that a heuristic approach is the best possible heuristic approach to problems of a particular class—which is not a good concrete example of satisficing!
maximization problems are characterized by searching over a set of potential solutions and generating a proof that a particular solution is the best of those solutions
You’re just saying that in this framework the function-to-be-optimized does not contain search/optimization costs. I think for most real-life optimization problems it’s a shortcoming :-)
I don’t believe the field of computational complexity makes reference to search/opportunity costs. As to whether this is a shortcoming, well, I’ll leave that to the professional mathematicians to decide.
Talking about computational complexity, I would probably put this one in the category of “satisficing,” since this is just a generalization of “good enough” from “objective value” to “convergence criterion.” It could be an optimality gap, the derivative of the objective function of found solutions, time since a new best solution was found, some complicated guess from solution space generalization, or so on.
(Another way to think about this is “acceptability” doesn’t have to apply to just the solution; it can also apply to the search process.)
You can just as easily put it into the category of “maximizing” since you’re maximizing your expected return (gain—costs).
In other frameworks, yes: a biologist or economist would think it natural to talk about real-world maximization (read: improvement) where costs are very relevant to profit.
In the framework of computational complexity, maximization problems are characterized by searching over a set of potential solutions and generating a proof that a particular solution is the best of those solutions. In the worst case where there is no structure on the set, that’s an O(N) operation (start at the first element in the set, compare the element in memory to element i+1 and put the bigger one in memory) on a set that’s typically exponential in problem size. So the generalization of expected return to maximization in this view is proving that a heuristic approach is the best possible heuristic approach to problems of a particular class—which is not a good concrete example of satisficing!
You’re just saying that in this framework the function-to-be-optimized does not contain search/optimization costs. I think for most real-life optimization problems it’s a shortcoming :-)
I don’t believe the field of computational complexity makes reference to search/opportunity costs. As to whether this is a shortcoming, well, I’ll leave that to the professional mathematicians to decide.