Cheap and Secure Web Hosting Provider : See Now

[Solved]: Minimize a sum with a weight constraint

, , No Comments
Problem Detail: 

We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$.

$M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$


$M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$

The problem is to select one and only one item from each set such that

$Min \{\displaystyle\sum_{j=1...N}(x_{i,j})\}$

s.t. $\displaystyle\sum_{j=1..N}(y_{i,j}) > R$

where $R$ is a given constant.

Is there any classic problem similar to this? or what is known about this class of problems?

Asked By : Farzad

Answered By : Shreesh

The problem you have given is similar to KNAPSACK as Yuval Filmus mentioned.

KNAPSACK problem is defined as:

maximize $\sum_{i=1}^n v_i x_i$
subject to $\sum_{i=1}^n w_i x_i \leq W$ and $x_i \in \{0,1\}. $

I assume the pair (0,0) is used so that you may not choose pairs for some of the $M_j$'s. Otherwise (0,0) pair is irrelevant in the problem.

If this is so, then your problem can be easily shown to be NP-complete. We can reduce KNAPSACK to your problem by taking $N=n$ and have each $M_j$ as a copy to the KNAPSACK instance (after negating $v_i$'s and $w_i$'s of course).

If pair (0,0) is not used in a way that I described above, then too you can circumvent the issue by adding $N$ pairs $(x_{N+i,j},y_{N+i,j})$, for $1\leq i \leq N$ in set $M_j$ for $1 \leq j \leq N$, so that each $M_j$ has now additional $N$ pairs (total of $2N+1$). Each $x_{N+i,j} = y_{N+i,j} = 0$ for all $i$'s and $j$'s.

If you say that each pair need to be distinct, then we can take $x_{N+i,j} = y_{N+i,j} = \epsilon_{i}$ to make each pair distinct, where $\epsilon_{i} \ll 1$ is an arbitrarily very small quantity. We also replace $R$ by $R+\Sigma_i \epsilon_i$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback