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!
-
$\begingroup$ @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. $\endgroup$IssamLaradji– IssamLaradji2016年02月08日 18:16:19 +00:00Commented Feb 8, 2016 at 18:16
-
$\begingroup$ @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. $\endgroup$IssamLaradji– IssamLaradji2016年02月08日 19:41:48 +00:00Commented Feb 8, 2016 at 19:41
-
$\begingroup$ 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.) $\endgroup$Raphael– Raphael2016年02月08日 21:21:59 +00:00Commented Feb 8, 2016 at 21:21
-
1$\begingroup$ Can't you solve this using a greedy approach? $\endgroup$Yuval Filmus– Yuval Filmus2016年02月08日 23:00:52 +00:00Commented Feb 8, 2016 at 23:00
-
$\begingroup$ @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! $\endgroup$IssamLaradji– IssamLaradji2016年02月09日 18:58:14 +00:00Commented Feb 9, 2016 at 18:58
2 Answers 2
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)$.
Explore related questions
See similar questions with these tags.