Erik van Holland — Contributions to Bin Packing Games
|Time:||Wednesday, July 4, 2012|
|Location:||Room 311, Citadel|
Consider a set of bins with capacity 1 and a set of items with possibly different sizes. These items can be packed into the bins and we consider two different ways of packing: An integer packing and a fractional packing. In both cases we maximize the total size of packed items and compare the corresponding maximum values.
It is conjectured that the difference, the so-called GAP, between these two optima is at most 1/7 times the optimum fractional value. Another conjecture states that the GAP is bounded by a universal constant. Although we were not able to prove or disprove these conjectures in general, we present some interesting instances and verify the above conjectures in some (small) cases. All in all, we try to gain some insight into the problem to stimulate further research.