Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with competitive analysis:
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 >>>

TR12-162 | 26th October 2012
Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock

The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity

Revisions: 1

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an ... more >>>

ISSN 1433-8092 | Imprint