3
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.