1
$\begingroup$

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!

$\endgroup$
  • $\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$ – Curious Feb 8 '16 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$ – Curious Feb 8 '16 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 Feb 8 '16 at 21:21
  • 1
    $\begingroup$ Can't you solve this using a greedy approach? $\endgroup$ – Yuval Filmus Feb 8 '16 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$ – Curious Feb 9 '16 at 18:58
2
$\begingroup$

A simple greedy approach works here: choose the $k$ elements having maximal $v_i L_i$.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.