Approximation for vector bin packing

Question

I came across the following question. Given a 2-approximation for minimum bin packing problem, find a 2d-approximation for d-dimensional bin backing.

To clarify, inputs to the bin packing problem are real numbers $x_1,...,x_n\in [0,1]$, which should be divided into $k$ bins $S_1,...,S_k$ such that for all $i$: $\sum\limits_{x\in S_i}x\le 1$.

Inputs to the vector bin packing problem are vectors $x_1,...,x_n\in [0,1]^d$, which should be divided into $k$ bins $S_1,...,S_k$ such that for all $1\le i \le k$ and $1\le j\le d$: $\sum\limits_{x\in S_i} x^j\le 1$, where $x^j$ is the $j'th$ coordinate of $x$.

It seems intuitive to use the 2-approximation on each coordinate of the given vectors $x_1,...,x_n\in [0,1]^d$ and obtain $d$ partitions into at most $2k$ bins (where $k$ is the minimal number of bins for the vectors partition). However, i cant seem to combine those bins into a partition of size at most $2d\cdot k$. For any vector $x_i\in [0,1]^d$, let $b_i\in \left\{1,...,2k\right\}^d$ be the vector whose $j'th$ entry is the bin in which $x_i^j$ was placed (after running the approximation on all the $j'th$ components). Since i cant allow two vectors $x_i,x_j$, whose corresponding vectors $b_i,b_j$ differ in at least one component, go into the same bin, it seems i need at least $(2k)^d$ bins. What am i missing?

Answer 1

Create an instance $y_1,\ldots,y_n$ of bin packing by taking $y_i = \max(x_i^1,\ldots,x_i^d)$, and solve it using the given approximation algorithm. The solution is feasible for the vector bin packing problem. On the other hand, given a solution for the vector bin packing problem, you can construct a solution for the "max" bin packing problem using at most a factor $d$ more bins by splitting each bin into $d$ bins according to the largest coordinate.