# Fast algorithm for max-convolution with concave functions?

I'm interested in a discrete max-convolution problem, which is to compute $$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right]$$ for all values $c=0, \ldots, C$, where $x=(x_1, \ldots, x_k)$ is a vector of non-negative integers.

If we assume that $f_k$ are all concave functions i.e., $f(i+1) - f(i) \le f(i) - f(i-1)$, how efficiently can $r = (r(0), \ldots, r(C))$ be computed?

Follow-up: what if $J$ of the $f_k$ functions are not concave?

• Possibly relevant paper: gams.com/~bussieck/TR-93-01.pdf – Craig Gidney Apr 8 '16 at 17:16
• @dan_x are you still interested for an answer? Did you manage to find one that would like to share with us? – Curious_Dim Jan 22 '18 at 1:12