# 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. – Curious Feb 8 '16 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. – Curious Feb 8 '16 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 '16 at 21:21
• Can't you solve this using a greedy approach? – Yuval Filmus Feb 8 '16 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! – Curious Feb 9 '16 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)$.