Department of
Applied
Mathematics

Bin Packing: Analysis of Online and Semionline Algorithms

Josef Bekesi

University of Szeged

Abstract

One-dimensional bin packing is a traditional combinatorical optimization problem. The classical version of the problem is the following: we have a list of real numbers from the interval (0,1] and we want to pack them into minimal number of unit capacity bins. Finding the optimal packing is known to be NP-hard. Consequently, a lot of research have been addressed to find polynomial time approximation algorithms with acceptable approximate behaviour. In this talk we overview some results on online and semionline algorithms for this problem. We introduce some well-known algorithms and present the most important ideas which are used in the analysis of these approximation algorithms.