Bin-packing with a capacity constraint on pairs of bins

Question

In the classic bin-packing problem, we have to pack some positive integers into bins, such that the sum in each bin is at most some constant $B$, and subjet to this, the number of bins is minimum.

Suppose now that we relax the capacity constraint: we only require that the sum in each pair of bins is at most $2 B$. For example: suppose the inputs are 9, 8, 7, 4 and $B=10$. With a constraint on each bin, we need 4 bins. With a constraint on each pair of bins, we need only 3 bins: {7,4}, {9}, {8}. Note that the sum of each pair of bins is at most 20.

What are some polynomial-time approximation algorithms for the relaxed problem?

WHAT I TRIED:

1. I looked at the Karmarkar-Karp bin packing algorithms. They find, in polynomial time, a solution with at most $OPT+\log^2(OPT)$ bins, where $OPT$ is the minimum number of bins. These algorithms crucially rely on configurations. A configuration is a multiset of items that can fit into a single bin (that is, a multiset of integers with sum at most $B$). A configuration for a pair of bins would be a multiset of integers with sum at most $2B$. But here, the constraint is on every pair (not just adjacent pairs), and it is not clear how to enforce this constraint. The same is true for most other algorithms that use configurations, such as the ones by de-la-Vega and Lueker, Hoberg and Rothvoss.

2. Let $L$ be the largest sum in the optimal bin-packing. We can find an approximate solution to the relaxed bin packing problem by guessing $L$:

• If $L\leq B$, then we run the KK bin-packing algorithm with capacity $B$.
• Otherwise, $B < L\leq 2 B$. Every other sum in the optimal packing must be at most $2 B - L$. Then, we run the KK bin-packing algorithm with one bin of capacity $L$ and as few bins as possible of capacity $2 B-L$.

The problem is that this algorithm is polynomial in $B$, which is pseudopolynomial in the problem size.

Is there a polynomial-time approximation algorithm, with guarantees similar to KK bin packing, for the relaxed bin-packing problem?

Answer 1

Let $OPT$ denote the optimal number of bins with original constraints.

Let $OPT'$ denote the optimal number of bins with relaxed constraints.

Note that $OPT' \geq OPT-2$.

Therefore, $KK$ bin packing algorithm also gives a solution to your problem of cost at most $OPT'$ + $O(\log^2(OPT'))$.

Answer 2

If I understand this correctly: Instead of packing everything into bins of size 10, I can either fit everything into one single bin of size 20, or into ONE bin of size 10+k plus any number of bins of size 10-k.

For a small size like B = 10, this might be quite easy in many cases: I use a simple algorithm, like first fit sorted, and prove that I can fit everything into n bins of size 10. Assume the total size is > 20. To get a result better than n, I could try to fit everything into one bin of size 11, and n-2 bins of size 9. This is not possible if the total size is greater than (n-2) * 9 + 11 = 9n - 7. But items with a total size of 9n - 7 would have most likely fit into n-1 bins of size 10. So it may be easy to show that the best solution is indeed with all bins having size 10.

This argument won't work well with large B.