2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\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.