1
$\begingroup$

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

$\endgroup$
2
  • 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$ May 22, 2018 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, 2018 at 20:26

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2020 at 20:22
  • $\begingroup$ @Steven, sorry, never seen it before (not that I can recall). $\endgroup$
    – D.W.
    Apr 2, 2020 at 21:12

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.