How to give an approximation algorithm for this unusual bin packing problem? The usual bin packing problem can be formulated as:
\begin{align}
 &amp; \underset{x,y}{\min}
 &amp; &amp; B = \sum_{i=1}^n y_i\\
 &amp; \text{subject to} 
 &amp; &amp; B \geq 1,\\
 &amp; &amp; &amp; \sum_{j=1}^n a_j x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}\\
    &amp; &amp; &amp; \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    &amp; &amp; &amp; y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    &amp; &amp; &amp; 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}
 &amp; \underset{x,y}{\min}
 &amp; &amp; B = \sum_{i=1}^n y_i\\
 &amp; \text{subject to} 
 &amp; &amp; B \geq 1,\\
 &amp; &amp; &amp; \sum_{j=1}^n a_{kj} x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}, \, \forall k \in \{1,\ldots,n\}\\
    &amp; &amp; &amp; \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    &amp; &amp; &amp; y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    &amp; &amp; &amp; 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?
Your problem is known as Multi-Capacity Bin Packing. One of the foundational papers in the area is by Leinberger, Karypis and Kumar, who state a result of Garey, Graham, Johnson and Yao that in the case of $d$ constraints (in your case, $d = n$) many natural algorithms give a $d+1$-approximation.