# Analysis of the following integer program

So the knapsack problem has an integer programming formulation as follows,

$$\max_x v\cdot x\\s.t \\x_i \in \{0,1\}\\w\cdot x \leq C$$

Now consider the second integer program which might be a variation of the knapsack integer program.

$$\max_x v\cdot x\\s.t \\x_i \in \{0,L_i\}\\ x_i \leq R \cdot \delta_i\\ \delta_i \in \{0,1\}\\ \sum_i \delta_i = k$$ where $v_i$ is item's $i$ value, $L_i$ and $k$ are constants, and $R = \max{\{L_1,L_2,...L_d\}}$.

• Is there a dynamic programming solution or an approximation algorithm for the second integer programming problem ?

• Is it possible to use the solution of the knapsack problem to warm
start or partially solve the second integer programming ?

Thanks!

• @YuvalFilmus, ops I messed up, now I believe it's fixed. :). Raphael The knapsack formulation is only there for the context (which might have defeated the purpose), the two questions are about the second integer programming formulation. Feb 8, 2016 at 18:16
• @Raphael, I am not trying to generalize the knapsack DP algorithm but I wondered if it's similar for the second IP. To give more context, I stumbled upon an optimization problem which I was able to formulate as the second IP above, and I was wondering if there are fast exact/approximate solutions to problems like that second IP. Thanks. Feb 8, 2016 at 19:41
• Well, I have not thought about this more deeply (and will not) but I note that having an IP formulation is probably not very conductive to algorithm design. An input-output specification of the problem is probably more useful. (I have no idea how to see from an LP or IP which algorithmic techniques apply to a problem.)
– Raphael
Feb 8, 2016 at 21:21
• Can't you solve this using a greedy approach? Feb 8, 2016 at 23:00
• @YuvalFilmus you are absolutely right. I can just take the top $k$ elements. I believe I formulated the integer problem wrongly, but the greedy approach should work for this one. Thanks for the eye opener! Feb 9, 2016 at 18:58

A simple greedy approach works here: choose the $k$ elements having maximal $v_i L_i$.
Yes, the problem can be solved with dynamic programming, in pseudo polynomial time. Let $f(j,k)$ be the largest value attainable for a particular value of $k$ when we constrain to use only the first $j$ elements of $x$ (i.e., when we are constrained to $x_{j+1} = x_{j+2} = \dots = x_d = 0$). Then you can express $f(j,k)$ in terms of values of the form $f(j',k')$ where $(j',k') \le (j,k)$. The running time will be $O(dk)$.