The usual bin packing problem can be formulated as: \begin{align} & \underset{x,y}{\min} & & B = \sum_{i=1}^n y_i\\ & \text{subject to} & & B \geq 1,\\ & & & \sum_{j=1}^n a_j x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}\\ & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\ & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\ & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\ \end{align}
where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$
I have a similar problem that is formulated as:
\begin{align} & \underset{x,y}{\min} & & B = \sum_{i=1}^n y_i\\ & \text{subject to} & & B \geq 1,\\ & & & \sum_{j=1}^n a_{kj} x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}, \, \forall k \in \{1,\ldots,n\}\\ & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\ & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\ & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\ \end{align}
where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$.
You can see that constraint 2 is no longer the same as in the usual formulation. Now, it must be satisfied for each item $k$.
In my problem the items influence each others (by constraint 2). Each item should be packed into a bin (by constraint 3). The objective is to minimize the number of bins used (by the objective function).
How can I solve this problem? Or how can I design an approximation algorithm for it?
I tired to apply the known approximation algorithm for bin packing such as (Next Fit, First Fit, etc.) but I failed because of constraint 2. (For example, I failed to give a proof of the approximation ratio 2 of Next Fit.)
Could you give me some directions where I should go (e.g., is this problem known) and how to solve this problem?
