Springe zum Hauptinhalt
Fakultät für Informatik

128. Informatik-Kolloquium

Frau Prof. P. Berenbrink

Simon Fraser University

"A Sublinear-Time Approximation Scheme for Bin Packing"

Dienstag, 11.12.2007
15:00 Uhr, 1/336

Alle interessierten Personen sind herzlich eingeladen!


The bin packing problem is defined as follows: given a set of n items with different sizes of at most one, find a packing of these items into minimum number of unit-size bins possible.

We present a sublinear-time asymptotic approximation scheme for the bin packing problem; that is, forany e>0, we present an algorithm A that has sampling access to the input instance and outputs a value k such that Opt<= k<= (1+e) Opt+1, where Opt is the cost of an optimal solution.

It is clear that uniform sampling by itself will not allow a sublinear-time algorithm in this setting; a small number of items might constitute most of the total weight and uniform samples will not hit them. In this work we use weighted samples, where item i is sampled with probability proportional to its weight. In addition to an approximate value to Opt, our algorithm can also output a constant-size ``template''

of a packing that can later be used to find a near-optimal packing in linear time