# Solution/Hardness of the following (integer) budgeted problem?

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$.

• What is the representation of $f_i$ in the problem? It seems that this can greatly affect the runtime – frogeyedpeas Jul 7 '16 at 21:57
• 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 – frogeyedpeas Jul 7 '16 at 21:59
• @frogeyedpeas I am not sure if there are inflection points on such integer/discrete functions? – user2789928 Jul 7 '16 at 22:14
• 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 – frogeyedpeas Jul 7 '16 at 22:19
• @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 Jul 7 '16 at 22:25

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.

• Thank you very much! Your explanation is excellent! The first part states very clearly that condition (iii) does not make this problem easier. – user2789928 Jul 8 '16 at 18:03
• But I am not sure about your second part, could you please comment on the answer by Chao? – user2789928 Jul 9 '16 at 20:16
• 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 Jul 9 '16 at 20:38

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.

• 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 Jul 9 '16 at 20:41
• Thank you very much! @Chaolu Xu, your answer is correct and extremely helpful! – user2789928 Jul 12 '16 at 1:37