2
$\begingroup$

I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f\colon M \rightarrow R^+$ mapping each number in $M$ to another positive number. We want to know if we can select non-repetitive numbers $a_1, \dots, a_n \in M$, such that the sum over the weighted prefix product $\sum_{i=1}^n f(a_i) \cdot \prod_{j=1}^{i} a_j$ is maximized. Does anyone know if this is NP-hard?

In particular, I'm interested in the case $f(a_i) = (1 - a_i)^2$.

$\endgroup$

1 Answer 1

3
$\begingroup$

This answer assumes that the numbers in $M$ are integers (it actually suffices for them to be at least $1$).

Suppose that $f$ is monotone increasing. This is the case of your example $f(a) = (a-1)^2$. In this case, your objective value is increasing in each coordinate, implying that $\{a_1,\ldots,a_n\}$ should be the $n$ largest numbers in $M$.

Now suppose that $a_1,\ldots,a_n$ is a solution. What happens when we switch $a_i$ and $a_{i+1}$? Denoting by $O$ the original value and by $S$ the new value, we have \begin{align} O - S &= \prod_{j<i} a_j \cdot \bigl(a_i f(a_i) + a_i a_{i+1} f(a_{i+1}) - a_{i+1} f(a_{i+1}) - a_i a_{i+1} f(a_i) \bigr) \\ &= \prod_{j<i} a_j \cdot \bigl( (a_i - 1) a_{i+1} f(a_{i+1}) - (a_{i+1} - 1) a_i f(a_i) \bigr). \end{align} Hence it is not worthwhile to do the switch if $$ (a_i - 1) a_{i+1} f(a_{i+1}) \geq (a_{i+1} - 1) a_i f(a_i) \stackrel*\Longleftrightarrow \frac{a_{i+1} f(a_{i+1})}{a_{i+1} - 1} \geq \frac{a_i f(a_i)}{a_i - 1}. $$ The asterisk is there since we cannot divide by zero. If $a_{i+1} = 1$ then the inequality always holds, and if $a_i = 1$ it is always OK to make the switch. This suggests that we interpret $\frac{af(a)}{a-1}$ as $\infty$ when $a = 1$.

The conclusion is that you should arrange the $a_i$ in non-decreasing order of $\frac{a_i f(a_i)}{a_i - 1}$: $$ \frac{a_1 f(a_1)}{a_1 - 1} \leq \cdots \leq \frac{a_n f(a_n)}{a_n - 1}. $$

For your particular choice of $f$, we have $$ \frac{a f(a)}{a-1} \stackrel*= a(a-1), $$ which is increasing in $a$. When $a = 1$, this conflicts with our interpretation of the fraction as infinity, but since $f(1) = 0$, it doesn't really matter where you put elements equal to $1$: their location doesn't effect the objective value. Therefore for this $f$, you should just arrange the $a_i$ in non-decreasing order. That is, $a_n,\ldots,a_1$ should be the $n$ largest elements of $M$.

$\endgroup$
2
  • $\begingroup$ I think when $f(a) = (a - 1)^2$, $f$ is not necessarily monotocially increasing when $a < 1$. $\endgroup$
    – Linda Cai
    Commented Mar 22, 2022 at 21:03
  • $\begingroup$ That's why I'm assuming that $M$ consists of integers. If that's not the case, you can still try to use the same technique and see if it still works. Apart from switching the location of two numbers in the chosen list $a_1,\ldots,a_n$, you can check when it is profitable to switch some $a_i$ with a completely different $a \in M$. $\endgroup$ Commented Mar 22, 2022 at 22:47

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.