Lately, I have been dealing with a problem that I didn't know how to name it to solve it properly.

The problem is as follow: let's assume that we have a set of elements $A$. And, we have two functions $f$ and $g$, where for any sub-set $B \subset A$ where $\left|B\right| < k$, $k$ is a constraint:

  1. $f(B)$ : estimates the gain obtained by the set $B$.
  2. $g(B)$ : estimates the loss obtained by the set $B$.

In our problem we have two strategies $S_1$, $S_2$ which depend on the circumstances of the environment

  1. $S_1$: selects a set $B_1$ that maximizes the gain
  2. $S_2$: selects a set $B_2$ that minimizes the loss

my strategy is a hybrid strategy selecting sets $B_1$ and $B_2$ where $\left|B_1\right|+\left|B_2\right|<k$, and we aim to maximize the gain and minimize the loss at the same time. My problem would be: $(max(f(B_1)), min(g(B_2))) s.t. \left|B_1\right|+\left|B_2\right|<k$

NT: given that there are several circumstances sometimes $S_1$ works more efficiently, and some cases $S_2$ works better

Is there anyone who knows what type of problem? Any documentation about it? Since it is an NP-hard problem, is there a way to find an approximation with in the optimal solution?

  • $\begingroup$ You are looking for the concept of "pareto optimal". $\endgroup$ – Sasha the Noob Jan 13 at 5:40
  • $\begingroup$ What do you mean by "optimal solution" ? Basically, you cannot maximize/minimize more than one variable. You have to define a fitness function, thas is to say a compromise, how much regret do you accept on $f$ to reduce how much $g$ ? Maybe you are just trying to maximize $f-g$ for instance... $\endgroup$ – Optidad Jan 13 at 9:53

Your Answer

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

Browse other questions tagged or ask your own question.