2
$\begingroup$

I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f: 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, \cdots, a_n \in M$, such that the sum over 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?

Edit: What about for some fixed $m \in [n]$ and $p \in (0, 1)$, maximizing $\sum_{i=1}^m f(a_i) \cdot \prod_{j=1}^{i} a_j + p \cdot \sum_{i=m+1}^n f(a_i) \cdot \prod_{j=1}^{i} a_j$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Theorem 1. The problem has an $O(m\log m)$-time algorithm, where $m=|M|$.

Proof sketch. Fix an instance of the problem. Assume without loss of generality that $M\subseteq (0, 1)$. (Otherwise an optimal solution $a_1,\ldots, a_n$ for $M$ can be obtained by computing an optimal solution $a'_1, a'_2, \ldots, a'_{n'}$ for $M'=M\cap (0, 1)$, then prepending the elements in $M\cap [1, \infty)$ in decreasing order.)

By rewriting, the problem is equivalent to finding $p=(p_1, p_2, \ldots, p_n) \subseteq M$ maximizing $$\text{value}(p) = \sum_{i=1}^n \big(\textstyle\prod_{j=1}^{i-1} p_j\big) (1-p_i) g(p_i),~~~~~~~~~(1)$$ where $g(z) = f(z)z/(1-z)$.


Remark for intuition. This interpretation is nice because then $\text{value}(p)$ is the expectation of the value returned by the following random process:

  1. for $i \gets 1, 2, \ldots, n$:
  2. $~~~$ with probability $1-p_i$, halt and return $g(p_i)$ (otherwise (with probability $p_i$) continue)
  3. return 0

With this interpretation, it is not too hard to see that we should use all elements of $M$ (in some order), and further that we should use them greedily---in order of decreasing $g(p_i)$. The proof below gives the details.


Here is the algorithm:

  1. let $q=(q_1, q_2, \ldots, g_m)$ be $M$ sorted by decreasing $g(q_i)$ (breaking ties arbitrarily).
  2. return $q$

Clearly this can be done in $O(m\log m)$ time. To finish we show that $q$ is an optimal solution.

By inspection of (1), there is an optimal solution that uses all elements of $M$ (as appending unused elements to any solution cannot decrease the cost). Let $p=(p_1, p_2, \ldots, p_m)$ be any such optimal solution. Define an inversion in $p$ to be a pair $i, j\in [m]$ such that $i < j$ and $r(i) > r(j)$, where $r(i)$ is the rank of $p_i$ in $q$ (so $q_{r(i)} = p_i$). If there are no inversions, then $p=q$ so $q$ is optimal, and we are done. Otherwise, there is an inversion $(i, i+1)$. Consider modifying $p$ by swapping $p_i$ with $p_{i+1}$. By calculation, this swap increases the solution value by $\prod_{j=1}^{i-1} p_j$ times $$ \begin{aligned} &(1-p_{i+1}) g(p_{i+1})+ p_{i+1} (1-p_i) g(p_i) \\ {}-{} & p_i (1-p_{i+1}) g(p_{i+1}) - (1-p_i) g(p_i) \\ {}={} & [g(p_{i+1}) - g(p_i)] (1-p_i)(1-p_{i+1}) \\ {}\ge{} & 0 & (\text{using } r(i) > r(i+1), \text{ so } g(p_i) \le g(p_{i+1})). \end{aligned} $$ So this swap reduces the number of inversions by one and yields another optimal solution. So repeatedly swapping yields an optimal solution $p$ with no inversions, i.e., with $p=q$, so $q$ is optimal.$~~~~\Box$

$\endgroup$
6
  • $\begingroup$ Thank you so much for this thorough response! I wasn't sure if it was easy or hard at first glance. $\endgroup$
    – Linda Cai
    Mar 22, 2022 at 21:01
  • $\begingroup$ Sure. One thing: in general it improves posts to add some context about where the problem comes from, what you've tried, and so on. See cstheory.stackexchange.com/help for more advice. $\endgroup$
    – Neal Young
    Mar 22, 2022 at 21:10
  • $\begingroup$ Yeah this makes sense! I will give more context in the future. (The original problem I was considering was that there are a bunch of boxes, each one with probability $p_i$ has a prize of value $h_i$, and remaining probability with nothing. Our task is to order them in advance and then inspect them one by one, once we see a prize we have to take it and leave. When we can order them however we like it's clear we should inspect box in decreasing $h_i$, but what if some of the boxes have fixed position that we cannot change? The special case of 1-box fixed can be converted to my posted Q. ) $\endgroup$
    – Linda Cai
    Mar 22, 2022 at 23:33
  • $\begingroup$ (Our objective is to have the highest expected prize value.) $\endgroup$
    – Linda Cai
    Mar 22, 2022 at 23:34
  • $\begingroup$ Interesting. How can the case with one box fixed be reduced to your posted question? If you'd like to ask about the more general question, I guess you can make another post. $\endgroup$
    – Neal Young
    Mar 23, 2022 at 2:28

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.