I'm interested in the following problem :

Input : an integer $n$, and $k$ increasing functions $f_i:\mathbb{N}\rightarrow\mathbb{R}$, such that $f_i(0)=0$ for all $1\le i \le k$

Output : $k$ integers $n_1,\dots,n_k$, such that $n_1+\dots+n_k=n$, with $0\le n_i\le n$

Goal : Maximize $\sum_{i}f_i(n_i)$

My question is : If we suppose that $k=n$, or simply $k=\Omega(n^\delta)$ for some $\delta>0$, is it possible to find the optimal solution in polynomial time (in $n$) ?

What if we first consider very simple functions like : $\forall i,m, f_i(m+1)-f_i(m)\in\{0,1\}$ ?

Such a result could possibly have interesting applications for dynamic programming

  • 3
    $\begingroup$ The "increasing" condition doesn't really restrict the range of functions that can be optimised: for any $k$ functions $g_i : \mathbb N \to \mathbb R$ whose absolute values are bound by some constant $M$ (i.e. without the increasing restriction), we can form a set of $k$ increasing functions $f_i$ by setting $f_i(x) = g_i(x) + x(M+1)$, and a partition of $n$ that maximises $\sum_i f_i(n_i)$ also maximises $\sum_i g_i(n_i)$ (which is equal to $\sum_i f_i(n_i) - n(M+1)$). $\endgroup$ – j_random_hacker May 22 '18 at 17:48
  • $\begingroup$ How are the functions specified in the input? As a truth table? (but that would take infinite size, so that can't be right) There seems to be no finite way to describe these functions that allows all functions to be specified. $\endgroup$ – D.W. May 22 '18 at 20:26

Yes. This can be solved in polynomial time using a straightforward dynamic programming algorithm. You build a table $A[\cdot,\cdot]$ where $A[i,m]$ denotes the maximal value of $f_1(n_1)+\dots+f_1(n_i)$ subject to the requirement that $n_1,\dots,n_i$ be a partition of $m$, i.e., $n_1 + \dots + n_i = m$. The entries satisfy the following recursive relation:

$$A[i,m] = \max \{A[i-1,m-t] + f_i(t) : 0 \le t \le m\}.$$

You can fill in this array using the recursive relation in $O(kn^2)$ time, which is polynomial in $n$. Then, $A[k,n]$ contains the answer to your problem.

  • $\begingroup$ I'm sorry for commenting to this old answer. Are you aware of a name for this problem/algorithm? Do you have a reference to a book where this/a similar problem is encountered? This seems pretty basic but I haven't been able to find it. $\endgroup$ – Steven Apr 2 '20 at 20:22
  • $\begingroup$ @Steven, sorry, never seen it before (not that I can recall). $\endgroup$ – D.W. Apr 2 '20 at 21:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.