I am looking for work done on solving a problem (specifically I'm looking for an approximation algorithm) which is very similar to a combination of two variations of the knapsack problem: maximum-density knapsack problem and multiple-choice knapsack problem.

The problem is:

We have $t$ sets $S_1,...,S_t$ of elements, where each set is of size $k$: $S_i=\{e_{i,1},e_{i,2},...,e_{i,k}\}$. for each element $e_{i,j}$ there is a profit $p_{i,j}$ and a cost $c_{i,j}$. It holds that $$c_{i_1,j}=c_{i_2,j},i_1 \neq i_2$$(the cost is the same for each set it only depends on the element's index in the set) so let us denote $c_{j}$ from now on. Both the Profit and the Cost are monotonically increasing: $$c_{j_1} \leq c_{j_2} \text{ if } {j_1} \leq {j_2}$$ $$p_{i, j_1} \leq p_{i, j_2} \text{ if } {j_1} \leq {j_2}$$
The problem is to choose one element from each set to construct a set of $t$ elemets ${e_{1,j_1},e_{2,j_2},...,e_{t,j_t}}$ with profits ${p_{1,j_1},p_{2,j_2},...,p_{t,j_t}}$ and costs ${c_{j_1},c_{j_2},...,c_{j_t}}$ such that the following exprssion is maximized: $$\frac{\sum_{i=1}^{t}p_{i,j_i}}{\sum_{i=1}^{t}c_{j_i}} = \frac{p_{1,j_1}+p_{2,j_2}+...+p_{t,j_t}}{{c_{j_1}+c_{j_2}+...+c_{j_t}}}$$
and the following expression holds for some constant $0 \leq r \leq 1$: $$ {\sum_{i=1}^{t}p_{i,j_i}} \geq r*{\sum_{i=1}^{t}p_{i,k}}$$

Intuitively, you need to maximize the ratio between the profit and the cost while having at least some portion of the profit.

As I said this problem can probably be reduced to a combination of maximum-density knapsack problem and multiple-choice knapsack problem, so any information on that (and not specifically on the problem I stated) can be helpful as well.

  • $\begingroup$ Do you have a specific question about your situation? I see a specification of a problem and some statements, but I don't see a concrete question. We're a question-and-answer site, so we require you to articulate a specific answerable question about your situation. Do you want to know whether it is in NP? whether it is NP-complete? for an approximation algorithm? something else? $\endgroup$ – D.W. Apr 12 '20 at 21:09
  • $\begingroup$ I want an approximation algorithm, sorry if that wasn't clear $\endgroup$ – Gilad Deutsch Apr 13 '20 at 16:12

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.