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?

  • $\begingroup$ Possibly relevant paper: gams.com/~bussieck/TR-93-01.pdf $\endgroup$ Apr 8, 2016 at 17:16
  • $\begingroup$ @dan_x are you still interested for an answer? Did you manage to find one that would like to share with us? $\endgroup$ Jan 22, 2018 at 1:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.