The Multiple-Choice Multi-Dimensional knapsack (MMKP) problem is defined as follows. The input is $N$ groups of items, each item in each group has a value, and requires $m$ resources. The total available resources is given by a vector $R = (r_1, r_2, .., r_m) $. The goal is to choose exactly one item from each group, such the the total value is maximized and the resource constraints hold.

If we would add to the problem the constraint that each item requires at most $n \ll m$ of the resources, will the new problem remain as hard as the original MMKP?

  • 1
    $\begingroup$ I suggest looking at the NP-hardness proof – perhaps it already satisfies the condition $n \ll m$. Also, to answer your question definitely, you will have to spell out what you mean be $n \ll m$ in concrete terms. $\endgroup$ – Yuval Filmus May 31 '17 at 16:09
  • $\begingroup$ I don't understand what is meant by "requires $m$ resources". Can you specify the problem more precisely? Don't force us to guess. What are the inputs? What would count as a valid solution? Also, is $n$ an input? Is $n$ a fixed constant? $\endgroup$ – D.W. May 31 '17 at 16:14

Your Answer

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

Browse other questions tagged or ask your own question.