0
$\begingroup$

What is the computational complexity of the calculation of $ \Psi(x) $ described below:

Let $\left\{ f_i : \{0,1,\dots,m\} \to \mathbb{R} \right\}_{i=1}^n$. For each $x \in \{0,1,\dots,m\}$ we consider $$ \Psi(x):= \min_{\begin{array}{c} \alpha_1x_1+\cdots+\alpha_n x_n=x \\ x_i\in \{0,1,\dots,m\}\\ \alpha_i \in \{0,1\} \end{array}}\sum_{i=1}^n f_i(x_i)$$

Improve this question
$\endgroup$
3
  • $\begingroup$ Why include $\alpha_i$? Simpler to have $$\Psi(x):= \min_{\begin{array}{c} x_1+\dots+x_n=x \\ x_i\in \{0,1,\dots,m\} \end{array}}\sum_{i=1}^n f_i(x_i)$$ $\endgroup$
    – RobPratt
    Commented Apr 7, 2021 at 15:05
  • $\begingroup$ The problem you say is not the original one. What you say is the infimal convolution. $\endgroup$
    – José María Grau Ribas
    Commented Apr 7, 2021 at 17:41
  • $\begingroup$ OK, I see. You have $f_i(x_i)$ and not $f_i(\alpha_i x_i)$. $\endgroup$
    – RobPratt
    Commented Apr 7, 2021 at 18:00

1 Answer 1

Reset to default
1
$\begingroup$

This is a variant of the integer equality knapsack problem and can be solved via dynamic programming. The complexity is described here.

For a DP recursion, first define $$\Psi_k(x):=\min_{\begin{array}{c} \alpha_1x_1+\cdots+\alpha_k x_k=x \\ x_i\in \{0,1,\dots,m\}\\ \alpha_i \in \{0,1\} \end{array}}\sum_{i=1}^k f_i(x_i)$$ and then condition on $\alpha_k$ and $x_k$ to obtain $$\Psi_k(x) = \min_{\alpha_k, x_k}\{f_k(x_k)+\Psi_{k-1}(x-\alpha_k x_k)\}$$ You want to compute $\Psi_n(x)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .