<p>Solving this exactly this ends up being $\mathsf{NP}$-hard.</p>

<p>The reduction I have doesn't pay much attention to the representation of the $f_i$'s. That said, the values of $f_i$ I end up giving can be computed efficiently, so this reduction works for any "black box" use of the $f_i$'s.</p>

<p>I'll give the reduction in two parts. Composing the two pieces gives the whole argument.</p>

<ol>
<li><p>Firstly I claim that condition (iii) doesn't help very much, even when combined with condition (i). In particular, there is a reduction from the problem with (iii) ignored to the original version of the problem: Suppose there is an instance with $f_i$'s that are non-decreasing but otherwise arbitrary. Then we can make a new instance (whose data is denoted with primes (')) which has</p>

<ul>
<li>$f_i'(0) \gets 0$,</li>
<li>for $x \ge 1$, $f_i'(x) \gets f_i(x-1) + A$ for an unspecified large constant $A$, and</li>
<li>$C_i' \gets C_i + 1$ and $C' \gets C + N$.</li>
</ul>

<p>Note that if a given $f_i$ is initially non-decreasing, then so is the new $f_i'$, while the rest of condition (i) holds for $f_i'$.</p>

<p>To satisfy condition (iii), it suffices to make $A$ large enough. This follows from thinking geometrically about what condition (iii) imposes on the $f_i$s. In particular, for any particular $x$, let $\ell$ be the line through the origin and $(x,f_i(x))$. The condition (iii) says that every point $x' \ge x$ must have $(x',f_i(x'))$ below $\ell$, and every point $x' \le x$ must have $(x',f_i(x'))$ above $\ell$. Thinking of increasing $A$ as pulling the origin down while fixing the rest of $f_i$, it's clear that this condition limits toward the empty constraint as $A$ increases, since the lines $\ell$ become arbitrarily steep.</p>

<p>We also need to ensure this reduction is actually a reduction. We can accomplish this also by making $A$ large enough. In particular, it's easy to see that if $A$ is sufficiently large, then any optimal solution of the new instance must invest at least one unit into each startup (ie $x_i' \ge 1$ for any $x'$ optimal in the new instance). Once we have this, identifying each solution $x$ to the original instance with the solution $x'$ of the new instance defined by $x'_i \gets x_i + 1$ gives a correspondence between optimal solutions.</p></li>
<li><p>Now, if we ignore condition (iii), we can easily reduce from knapsack by making each $C_i$ the weight of item $i$, $C$ the capacity of the knapsack, and each $f_i$ "all-or-nothing" ($f_i(C_i) = C_i$ and $f_i(x) = 0$ otherwise). Then maximizing $\sum_i f_i(x_i)$ boils down to picking items that go into the knapsack. This is (in my opinion) easy to check and not the interesting part of this answer, so I won't belabor the details.</p></li>
</ol>

CC BY-SA 3.0
2016-07-08T18:03:45.207Z
Thank you very much! Your explanation is excellent! The first part states very clearly that condition (iii) does not make this problem easier.
user2789928
CC BY-SA 3.0
2016-07-09T20:16:47.003Z
But I am not sure about your second part, could you please comment on the answer by Chao?
user2789928
CC BY-SA 3.0
2016-07-09T20:38:08.563Z
There is no contradiction between his answer, mine, and assuming P!=NP. It's virtually the same as the situation for knapsack itself: the problem is NP-hard when you allow for numeric inputs of polynomial bit length, but easy if you require the numeric inputs to be bounded by a polynomial in actual value. In particular, the reduction in my answer typically gives exponentially large values of C, while Chao's algorithm can be made to work whenever C is bounded by a polynomial (no matter how the $f_i$s are encoded).
Andrew Morgan
CC BY-SA 3.0
2016-07-08T13:32:12.953Z
2016-07-08T13:32:12.953Z
Andrew Morgan
<p>The representation of $f_i$ matters. If $f_i$ is given as the list of values $f_i(0),\ldots,f_i(C_i)$, then the problem is in $P$. </p>

<p>Let $D(k,b)$ to be the maximum value of $\sum_{i=1}^k f_{i}(x_i)$
under the constraint
$\sum_{i=1}^k x_i = b$.
The answer you looking for is $\max \{ D(N,b) | b\leq C\}$.</p>

<p>One can write a recurrence for $D(k,b)$ use idea similar to the knapsack problem. It's not difficult to get $O(NC^2)$ time.</p>

CC BY-SA 3.0
2016-07-09T20:41:36.857Z
As a note: if $C$ is polynomially bounded in actual value (as is implicitly the case in this input format), then you can easily translate any representation of the $f_i$s to the explicit one here, and then apply the DP solution.
Andrew Morgan
CC BY-SA 3.0
2016-07-12T01:37:12.680Z
Thank you very much! @Chaolu Xu, your answer is correct and extremely helpful!
user2789928
CC BY-SA 3.0
2016-07-09T05:28:27.723Z
2016-07-09T05:28:27.723Z
Chao Xu
<p>I have no idea how to solve the following <strong>INTEGER</strong> problem or prove its hardness. Thanks for any help/comment/open discussion!</p>

<p>Assume there are $N$ startups. For each startup $i$, you can invest $x_i\in \{0,1,...,C_i\}$ dollars where $C_i$ is the maximal investment that it accepts, and you will get a reward as $f_i(x_i)$. The reward function $f_i(x_i)$ has the following properties for all $i$:</p>

<p>(1) $f_i(.)$ is non-decreasing and $f_i(0)=0$</p>

<p>(2) $f_i(.)$ is not necessarily "convex" or "concave"</p>

<p>(3) $0 \leq x\leq x'\leq C_i$, $f_i(x)x' \geq f_i(x')x$</p>

<p>(4) the function $g_i(x) = f_i(x+1) - f_i(x)$ is not necessarily non-decreasing or non-increasing.</p>

<p>Your total budget is $C$. By selecting an <strong>INTEGER</strong> vector $(x_1,...,x_N)$, you want to maximize the total rewards $\sum_{i=1}^Nf_i(x_i)$ subject to (1) $x_i\in \{0,1,...,C_i\}$ for any $i$ and (2)$\sum_{i=1}^N x_i \leq C$.</p>

CC BY-SA 3.0
2016-07-07T21:57:47.273Z
What is the representation of $f_i$ in the problem? It seems that this can greatly affect the runtime
Sidharth Ghoshal
CC BY-SA 3.0
2016-07-07T21:59:14.477Z
For example if the $f_i$ are given as polynomials, then we know for fact that the number of inflection points is polynomial in the size of the representation of the function, but other formats might result in exponentially many inflection points, and make optimization much trickier
Sidharth Ghoshal
CC BY-SA 3.0
2016-07-07T22:14:56.610Z
@frogeyedpeas I am not sure if there are inflection points on such integer/discrete functions?
user2789928
CC BY-SA 3.0
2016-07-07T22:19:01.713Z
Agreed, that's more of a continuous word, but what I mean to ask can be restated (now meaningful in the discrete realm): does $g_i$ have arbitrarily many points where it changes sign? If the $f_i$ are represented as polynomials in algebraic form, then $g_i$ can only change sign a polynomial number of times in the size of $f_i$ and so a brute force search at each "change sign" point becomes feasible. But if $f_i$ admit a more complicated representation, then this becomes a much harder problem
Sidharth Ghoshal
CC BY-SA 3.0
2016-07-07T22:25:56.480Z
@frogeyedpeas $g_i(.)$ is always non-negative as $f_i(.)$ is non-decreasing. Can you provide more details on the brute force algorithm? It is not bad if the complexity contains some factor like $O(C^2)$
user2789928
CC BY-SA 3.0
2016-07-07T22:33:59.410Z
Actually with second thought, I see the idea I had, only applies in continuous optimization, this gets much trickier in the discrete realm
Sidharth Ghoshal
CC BY-SA 3.0
2016-07-08T16:05:42.907Z
When x=0 then what does your third condition mean?
Saeed
CC BY-SA 3.0
2016-07-08T16:39:27.213Z
@Saeed good catch! I modified it.
user2789928
<ds.algorithms><np-hardness><approximation-algorithms><optimization>
Solution/Hardness of the following (integer) budgeted problem?
user2789928
# Solution/Hardness of the following (integer) budgeted problem?

(Asked by: username_0 on 2016-07-07)

I have no idea how to solve the following **INTEGER** problem or prove its hardness. Thanks for any help/comment/open discussion!

Assume there are $N$ startups. For each startup $i$, you can invest $x\_i\in \{0,1,...,C\_i\}$ dollars where $C\_i$ is the maximal investment that it accepts, and you will get a reward as $f\_i(x\_i)$. The reward function $f\_i(x\_i)$ has the following properties for all $i$:

(1) $f\_i(.)$ is non-decreasing and $f\_i(0)=0$

(2) $f\_i(.)$ is not necessarily "convex" or "concave"

(3) $0 \leq x\leq x'\leq C\_i$, $f\_i(x)x' \geq f\_i(x')x$

(4) the function $g\_i(x) = f\_i(x+1) - f\_i(x)$ is not necessarily non-decreasing or non-increasing.

Your total budget is $C$. By selecting an **INTEGER** vector $(x\_1,...,x\_N)$, you want to maximize the total rewards $\sum\_{i=1}^Nf\_i(x\_i)$ subject to (1) $x\_i\in \{0,1,...,C\_i\}$ for any $i$ and (2)$\sum\_{i=1}^N x\_i \leq C$.

**Tags:** ds.algorithms, np-hardness, approximation-algorithms, optimization

> **Comments:**
> **username_1**: What is the representation of $f_i$ in the problem? It seems that this can greatly affect the runtime  
> **username_1**: For example if the $f_i$ are given as polynomials, then we know for fact that the number of inflection points is polynomial in the size of the representation of the function, but other formats might result in exponentially many inflection points, and make optimization much trickier  
> **username_0**: @frogeyedpeas I am not sure if there are inflection points on such integer/discrete functions?  
> **username_1**: Agreed, that's more of a continuous word, but what I mean to ask can be restated (now meaningful in the discrete realm): does $g_i$ have arbitrarily many points where it changes sign? If the $f_i$ are represented as polynomials in algebraic form, then $g_i$ can only change sign a polynomial number of times in the size of $f_i$ and so a brute force search at each "change sign" point becomes feasible. But if $f_i$ admit a more complicated representation, then this becomes a much harder problem  
> **username_0**: @frogeyedpeas $g_i(.)$ is always non-negative as $f_i(.)$ is non-decreasing. Can you provide more details on the brute force algorithm? It is not bad if the complexity contains some factor like $O(C^2)$  
> **username_1**: Actually with second thought, I see the idea I had, only applies in continuous optimization, this gets much trickier in the discrete realm  
> **username_2**: When x=0 then what does your third condition mean?  
> **username_0**: @username_2 good catch! I modified it.  

---

## 2 answers

### Answer by username_3 on 2016-07-08. Score: 4 | Accepted answer

Solving this exactly this ends up being $\mathsf{NP}$-hard.

The reduction I have doesn't pay much attention to the representation of the $f\_i$'s. That said, the values of $f\_i$ I end up giving can be computed efficiently, so this reduction works for any "black box" use of the $f\_i$'s.

I'll give the reduction in two parts. Composing the two pieces gives the whole argument.

1. Firstly I claim that condition (iii) doesn't help very much, even when combined with condition (i). In particular, there is a reduction from the problem with (iii) ignored to the original version of the problem: Suppose there is an instance with $f\_i$'s that are non-decreasing but otherwise arbitrary. Then we can make a new instance (whose data is denoted with primes (')) which has

   * $f\_i'(0) \gets 0$,
   * for $x \ge 1$, $f\_i'(x) \gets f\_i(x-1) + A$ for an unspecified large constant $A$, and
   * $C\_i' \gets C\_i + 1$ and $C' \gets C + N$.

   Note that if a given $f\_i$ is initially non-decreasing, then so is the new $f\_i'$, while the rest of condition (i) holds for $f\_i'$.

   To satisfy condition (iii), it suffices to make $A$ large enough. This follows from thinking geometrically about what condition (iii) imposes on the $f\_i$s. In particular, for any particular $x$, let $\ell$ be the line through the origin and $(x,f\_i(x))$. The condition (iii) says that every point $x' \ge x$ must have $(x',f\_i(x'))$ below $\ell$, and every point $x' \le x$ must have $(x',f\_i(x'))$ above $\ell$. Thinking of increasing $A$ as pulling the origin down while fixing the rest of $f\_i$, it's clear that this condition limits toward the empty constraint as $A$ increases, since the lines $\ell$ become arbitrarily steep.

   We also need to ensure this reduction is actually a reduction. We can accomplish this also by making $A$ large enough. In particular, it's easy to see that if $A$ is sufficiently large, then any optimal solution of the new instance must invest at least one unit into each startup (ie $x\_i' \ge 1$ for any $x'$ optimal in the new instance). Once we have this, identifying each solution $x$ to the original instance with the solution $x'$ of the new instance defined by $x'\_i \gets x\_i + 1$ gives a correspondence between optimal solutions.
2. Now, if we ignore condition (iii), we can easily reduce from knapsack by making each $C\_i$ the weight of item $i$, $C$ the capacity of the knapsack, and each $f\_i$ "all-or-nothing" ($f\_i(C\_i) = C\_i$ and $f\_i(x) = 0$ otherwise). Then maximizing $\sum\_i f\_i(x\_i)$ boils down to picking items that go into the knapsack. This is (in my opinion) easy to check and not the interesting part of this answer, so I won't belabor the details.

> **Comments:**
> **username_0**: Thank you very much! Your explanation is excellent! The first part states very clearly that condition (iii) does not make this problem easier.  
> **username_0**: But I am not sure about your second part, could you please comment on the answer by Chao?  
> **username_3**: There is no contradiction between his answer, mine, and assuming P!=NP. It's virtually the same as the situation for knapsack itself: the problem is NP-hard when you allow for numeric inputs of polynomial bit length, but easy if you require the numeric inputs to be bounded by a polynomial in actual value. In particular, the reduction in my answer typically gives exponentially large values of C, while Chao's algorithm can be made to work whenever C is bounded by a polynomial (no matter how the $f_i$s are encoded).  

---

### Answer by username_4 on 2016-07-09. Score: 3

The representation of $f\_i$ matters. If $f\_i$ is given as the list of values $f\_i(0),\ldots,f\_i(C\_i)$, then the problem is in $P$.

Let $D(k,b)$ to be the maximum value of $\sum\_{i=1}^k f\_{i}(x\_i)$
under the constraint
$\sum\_{i=1}^k x\_i = b$.
The answer you looking for is $\max \{ D(N,b) | b\leq C\}$.

One can write a recurrence for $D(k,b)$ use idea similar to the knapsack problem. It's not difficult to get $O(NC^2)$ time.

> **Comments:**
> **username_3**: As a note: if $C$ is polynomially bounded in actual value (as is implicitly the case in this input format), then you can easily translate any representation of the $f_i$s to the explicit one here, and then apply the DP solution.  
> **username_0**: Thank you very much! @Chaolu Xu, your answer is correct and extremely helpful!  

---

