patternMinor
Minimize a sum with a weight constraint
Viewed 0 times
minimizesumwithweightconstraint
Problem
We are given
$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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#53977, answer score: 5
Revisions (0)
No revisions yet.