128. Informatik-Kolloquium
Frau Prof. P. Berenbrink
Simon Fraser University
Canada
"A Sublinear-Time Approximation Scheme for Bin Packing"
Dienstag, 11.12.2007
15:00 Uhr, 1/336
Alle interessierten Personen sind herzlich eingeladen!
Abstract:
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
