MAXIMUM CLASS-CONSTRAINED KNAPSACK

• INSTANCE: n set sizes specified by an n-vector $U \in N^n$, m knapsacks with different volumes and number of compartments specified by two m-vectors $V \in N^m, C \in N ^m$, such that $\sum_i U_i = \sum_j V_j$.

• SOLUTION: A placement of the set elements into the knapsacks, specified by two $n\times m$-matrices: $I \in \{0,1\}^{n\times m}, Q \in N ^{n\times m}$, such that: $\sum_i Q_{i,j} \le V_j$ and $\sum_i I_{i,j} \le C_j$ for every j, $\sum_j Q_{i,j} \le U_i$ for every i, and $I_{i,j}=0 \Rightarrow Q_{i,j}=0$ for every (i,j).

• MEASURE: Total number of packed elements, i.e., $\sum_i \sum_j Q_{i,j}$.

  
  

• Good News: Approximable with an absolute error guarantee of $\sum_{j=1}^N \frac{V_j}{C_j+1}$ [437].