Bin Packing with Advice

Abstract

"The framework of competitive analysis is often used to study the bin packing algorithms. Under this framework, the behavior of online algorithms is compared to an optimal offline algorithm on the worst possible input. In this thesis, we discuss the limitations of the competitive analysis and introduce the bin packing problem under the advice model. In competitive analysis, the focus on improving competitive ratio often results in sacrificing the average-case performance and therefore, many of the studied online algorithms have no practical significance.

An alternative for analysis of online problems is the advice model which has received significant attention in the past few years. Under the advice model, an online algorithm receives a number of bits of advice about the unrevealed parts of the sequence. Generally, there is a trade-off between the size of the advice and the performance of online algorithms.

The main goal of this thesis is to find whether the entire input distribution is required to improve the competitive ratio of an online algorithm or only partial information about the distribution is sufficient to improve the performance. It turns out that information about some portion of the distribution is enough to achieve reasonable competitive ratio. We have designed a heuristic under the assumption of such advice and compared its performance against standard bin packing heuristics.