Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Online algorithm:
TR01-085 | 1st October 2001
Gerhard J. Woeginger

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource
augmentation model of competitive analysis.
In this model, the online bounded space packing algorithm has
to pack a list L of items in (0,1] into a small number of
bins of size b>=1.
Its performance is measured by comparing the ... more >>>

TR06-112 | 22nd August 2006
Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang

Strip Packing vs. Bin Packing

In this paper
we establish a general algorithmic framework between bin packing
and strip packing, with which we achieve the same asymptotic
bounds by applying bin packing algorithms to strip packing. More
precisely we obtain the following results: (1) Any offline bin
packing algorithm can be applied to strip packing ... more >>>

ISSN 1433-8092 | Imprint