On 07.11.2013 at 12:20 in S6, there is the following noon lecture:
Bin Packing: Analysis of Online and Semionline Algorithms
University of Szeged
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010