snippetMinor
How to give an approximation algorithm for this unusual bin packing problem?
Viewed 0 times
thisunusualproblemapproximationbingivepackingalgorithmforhow
Problem
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?
\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?
Solution
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.
Context
StackExchange Computer Science Q#54674, answer score: 5
Revisions (0)
No revisions yet.